Number theory demystified  Ankan Sengupta, FMS Delhi

Number theory has always been a chapter which is fascinating if can be learnt properly, otherwise it might become nightmarish and can well prove to be the bane in a competitive exam like CAT, where you’ll find a chunk of question on this topic every year. In this article I’ll discuss a few topics along with some tricks to make others help grapple this superlative topic with some ease at least.
Number theory problems are of 3 types mainly. Basic concepts based, Remainder problems and LCMHCF based problems. I’ll discuss all 3 of them.
Basic Concept based problems: Now a days most of the questions come from this area only cause there is no fixed set of formulae to solve problems of this area. So what you need is to have a clear understanding of the basics. Take for example:
For how many natural numbers n (n+36) is a perfect square ?
a) 0
b) 1
c) 2
d) None of the aboveAns: Case 1:both n and n+36 are perfect squares. Only 1 possible case,that is n = 64.
Case 2: n+36=kn, where k is a perfect square.so k=1+36/n.Factors of 36 are 1,2,3,4,6,9,12,18 and 36. Only when n=12,k is a perfect square. So combining these 2 cases we can say option C is correct.
A clarity of basics is the imperative tool to be able to decipher all the cases. If you miss even a single case,that might lead to a 1 instead of a clearcut +3. People who are prone to silly mistakes watch out for keywords like,natural numbers/real numbers/integers while solving this type of questions.
Now I want to discuss one of favourite questions in this topic.
In how many ways can you express 72 as product of 3 natural numbers( unordered pairs)
If there is a triplet (a,b,c), then an ordered triplet means (a,b,c) and (b,a,c) are different and an unordered triplet means (a,b,c),(b,a,c),(c,a,b) etc all are same.
72 = 2^3 * 3^2
let, x = 2^a1 * 3^b1
y= 2^a2 * 3^b2
z = 3^a3 * 3^b3
a1+a2+a3=3..solutions=3+31C31= 10
b1+b2+b3=2 solutions=3+21C31= 6
total solutions=10*6= 60( these are ordered pairs)Some of the solutions will be 1*1*72, 2*2*18 ..there will 4 such numbers since 4 factors of 72 are perfect squares...these numbers can be arranged in 3!/2! =3 ways...
603*4=48..these 48 is ordered pairs with all numbers different..so divide by 3!..48/6=8. add the remaining 4 we removed 8+4=12.Now what we did in the step before the last one is to remove repetitive elements.A simple way to do that is to check how many perfect squares are there in the number given.
Like in 72=2^3*3^2,there 2*2=4 perfect squares(Every even power including 0 of a prime factor gives rise to a perfect square,so contributions of 2’s power=2,contribution of 3’s power=2).
Now since 72 is not a perfect cube so all the 3 numbers cannot be equal,atmost 2 can be equal.When 2 of the numbers are equal,total number of arrangements is 3!/2!=3.so these 3*4=12 elements are repetitive.So primarily just subtract these 12 elements from total 60 and divide the residue by 3!(since there are 3 number so divide the ordered unequal numbers by 3! To get the unordered one).So total unordered unequal solutions=48/6=8.Now add back those 4 repititive elements here.so total 8+4=12 solutions.
This is the most complex problem of this portion.Will end this part with another problem with slightly different flavour.
A * B = 9C + 1 where A, B and C are natural numbers and A lies between 100 and 200 both inclusive. How many different values can A take.
a) 101
b) 50
c) 11
d) none of the aboveA=100+x,where x is a whole number and < =100.
so (100+x)B1/9=C to have an integral value of C, (1+x)B1=9k, k=positive integer.
now if (1+x)=3m form,then 3m1 cannot be equal to 9k.
so except for 3m form,3m+1 and 3m+2 both forms are permissible.
so 1+x=3m,x=3m1=3n+2.
so all the whole numbers between 0 and 100,which are of the form 3n+2 need to be excluded.
so 10133=68 should be the answer.Incorporated this question just to show how clarity in basics is a prerequisite in this topic.
Remainder problems:
Now a days CAT doesn’t emphasize on this portion much cause by cramming a few formulae you can tackle all the questions. Still would like to discuss 2 topics here: Chinese remainder theorem(CRT) and modified Euler function/modified cyclicity/charmichael’s function.
a) CRT:
Find the last 3 digits of 126^130.
Ans:there are many ways to solve this question.but easiest way is to use CRT.
See in CRT what we do is to express the divisor as a product of 2 coprime integers. Now we’ve to find last 3 digits,that means we’ve to divide the number given by 1000.1000=125*8 (125 and 8 are coprimes).
Now divide the number given by 125.remainder is 1.
And again divide the number given by 8. Remainder is 0.Now this is the most important part.By the help of CRt we can say that the ultimate remainder that we require is of the form 125k+1=8m,where k,m are nonnegative integers..376 is the first number of this form. So 376 is our answer.This is how CRT works.
b) Cyclicity:
Now I’ll discuss a trick that reduces our effort in problems where we generally employ Euler’s theorem.
The use will be just like Euler.Just instead of calculating Euler’s totient function, we’ll compute cyclicity.
C(P^n)=P^n(11/P)[P=prime,not for 2]
C(2^n)=2^(n1)[n
C(2^n)=2^(n2)[n>=3]
C (any composite number say P^n*Q^k*R^m) = LCM{C(P^n),C(Q^k),C(r^m)}[P,Q,R are prime factors of that composite number]
Say for example
25^19mod36find remainder.
In this problem E(36)=12.When you divide the exponent with 12 remainder is 7,so you still have to do some calculation. Now C(36)=LCM{C(3^2),C(2^2)}=6.when you divide the power by 6,it becomes 1.So simply the remainder becomes 1.
By Euler you’ll get the same answer,but it reduces your effort significantly.
c) LCMHCF/factor based problems:
Here I’ll discuss 2 of my favourite type of problems.
First question incorporates both the concept of LCM and remainder.
I thought of a number that when divided by 20 leaves a remainder 18,when divided by 19 remainder is 17 and so on .So what is the remainder when smallest such number is divided by 50?
Ans: This question checks our basics very nicely.
We can say if the number is N,N+2 is divisible by 2,3,4,5,6…,20.so LCM of all these numbers=2^4*3^2*5*7*11*13*17*19.
So N=the number mentioned2.
Now last 2 digits of the number mentioned above=10 (we can get that by simple remainder theorem).
So last 2 digits of N=08.So if we divide a number by 50 whose last 2 digits=08, remainder will always be 08.So this is the ans.
Second problem involves your thinking regarding multiplication along with factorisation.N=2^3*3^4*5^9.Fins the number of zeroes in the product of all the factors of this number that are not divisible by 12.
Ans: No of factors of this number=4*5*10=200
Number of factors divisible by 12=2*4*10=80
Product of all factors=N^no of factors/2=N^100
Product of all factors divisible by 12=(12N)^40
Product of factors not divisible by 12=N^100/(12N)^40=N^60/12^40=2^100*3^80*5^540
So number of zeroes=min(100,540)=100.This example sums up all the queries regarding questions on factorisation.
These are the main topics that you’ve to cover in number theory and trust me if your basics are clear Number Theory is the most interesting topic that you’ll come across in mathematics.
One more topic I’d like to mention here in a short way.
Perfect number is defined as a positive integer which is the sum of its proper positive divisors, that is, the sum of the positive divisors excluding the number itself.First four perfect numbers can be generated by 2^{n}^{−1}(2^{n} − 1).[Where 2^{n} − 1 is a prime number].
This are all even perfect numbers.All even perfect numbers (except 6) digital root 1.6,28,496,8128 are perfect numbers. The reciprocals of the divisors of a perfect number N must add up to 2.If you can remember these properties you’ll surely be benefited on the long run.For more enthusiastic readers,some suggested topics are:Charmichael’s function,Chicken Mcnugget’s theorem,Number of Ordered and unordered pairs in a given LCM of 3 or more numbers,Concepts regarding Armstrong number,Factorian etc.
Happy learning.