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 LCM-HCF 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 above

    Ans: 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 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 clear-cut +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 10
    b1+b2+b3=2 solutions=3+2-1C3-1= 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...
    60-3*4=48..these 48 is ordered pairs with all numbers 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! 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 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 above

    A=100+x,where x is a whole number and < =100.
    so (100+x)B-1/9=C to have an integral value of C, (1+x)B-1=9k, k=positive integer.
    now if (1+x)=3m form,then 3m-1 cannot be equal to 9k.
    so except for 3m form,3m+1 and 3m+2 both forms are permissible.
    so 1+x=3m,x=3m-1=3n+2.
    so all the whole numbers between 0 and 100,which are of the form 3n+2 need to be excluded.
    so 101-33=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 co-prime 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 co-primes).
    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 non-negative 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(1-1/P)[P=prime,not for 2]



    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^19mod36-find 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) LCM-HCF/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…, LCM of all these numbers=2^4*3^2*5*7*11*13*17*19.
    So N=the number mentioned-2.
    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 2n−1(2n − 1).[Where 2n − 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.

Log in to reply