Collection of Number Theory Concepts  Maneesh

(1) The number of divisors of a given number N (including 1 and the number itself) where N = a^m * b^n * c^p where a, b and c are prime numbers Is (1+m)(1+n)(1+p).
Find the number of divisors of 120
120 = 2^3 * 3 * 5
number of divisors = 4 * 2 * 2 = 16(2) In the above case, sum of divisors is ((a^(m+1) )1)/(a – 1) * ((b^n+1)1)/(b1) * ((c^(p+1) 1 )/(c1)
Find the sum of divisors of 120
120 = 2^3 * 3 * 5
sum = 2^4 – 1 / 1 * 3^21/2 * 5^2 – 1 / 4 = 15 * 4 * 6 = 360(3) The number of ways in which a number N can be expressed as the product of two factors which are relatively prime to each other is 2^(m1) where m is the number of different prime factors of N.
The number of ways 120 can be expressed as the product of two factors which are relatively prime to each other
120 = 2^3 * 3 * 5
Number of prime factors = 3
number of ways = 2^2 = 4
{ (1,120),(3,40),(5,24),(8,15)}(4) Product of factors of N = N^(f/2) where f is number of factors .
Find the product of factors of 24
24 = 2^3 * 3
Number of factors = 4 * 2 = 8
product = 24^4(5) N = 2^3 * 3^4 * 5^9
Find the product of all factors of N which are not divisible by 12Number of factors = 4 * 5 * 10 = 200
Product of factors = 2^300 * 3^400 * 5^900
Number of factors which are divisible by 12 = 2 * 4 * 10 = 80
Product of factors which are divisible by 12 = 2^40 * 3^120 * 5^360 * 12^80
Required product = 2^300 * 3^400 *5^900 / 2^40 * 3^120 * 5^360 * 2^160 *3^80
= 2^100 * 3^200 * 5^540(6) N = 2^15 * 3^12 How many factors of N^2 are less than N but do not divide N completely?
Factors of N = 16 * 13 = 208
Factors of N less than N = 208  1 = 207
Factors of N^2 = 31 * 25 = 775
Factors of N^2 less than N = (775  1)/2 = 387
So ans = 387 – 207 = 180(7) Number of Weighing
If N is the number of balls and question doesn’t specify whether the ball weighs more or less, Then total number of weighing = m+1
Where N < = 3^m+3^(m1)+3^(m2) +…. + 3^0
If the question specifies that ball weighs more or less then total number of weighing = m
Where N < = 3^m(a) There are 47 identical coins. All the coins have same weight except one coin which has a different weight. What's the minimum number of weighing required to be certain of identifying the coin with different weight?
1+3+9+27 = 40
1+3+9+27+81 = 121> 47
So here m= 4
Number of weighing required m+1 = 5(b) You have 80 pearls . One is lighter than remaining.Minimum number of weighing required on a common balance to ensure that odd pearl is identified ?
80 < = 81 so m = 4
Number of weighing required =4(8) Euler’s theorem
Euler’s function E[n] denotes number of positive integers that are coprime to and less than a certain positive integer ‘n’ .
Prime divisors of 100 are 2 and 5.
So number of integers less than 100 and not divisible by 2 or 5 are
100  100/2  100/5 + 100/2*5
= 100(11/2) ( 11/5)In general a positive integer N having prime divisors p1, p2, p3 … pn
E[N] = N(11/p1)(11/p2) ... (11/pn)
Euler’s theorem states that:
If P and N are postitve coprime integers then p ^E[N] mod N = 1
Where E[N] is the Euler’s function for N.9^101 mod 125
E[125] = 125 * 4/5 = 100
Since 9 and 125 are coprime , 9^100 mod 125 = 1
so remainder is 9 * 1 = 9(9) Sum of all coprimes of N which are less than N = N * E(N)/2
Sum of coprimes of 377 which are less than 377?
E[377] = 377 * 28 * 12/29 * 13 = 336
Sum = 377 * 336/2 = 63336
another way also this can be done
Sum = [1+2+3….376] – [sum of all multiples of 29]  [sum of all multiples of 13](10) Wilson Theorem
If P is a prime number, (P1)! +1 is divisible by P
(P1)! Mod P = 1 or (P1)
(P2)! Mod P = 1
(p3)! Mod P = (p1)/216! = (16!+1)1 = (16!+1)+1617
16! Mod 17 = 0 + 16  0 = 1615! Mod 17 => 16!mod 17 = 16
15! * 16 mod 17 = 16
15! Mod 17 =114! Mod 17 > 15! Mod 17 = 1
14! * 15 mod 17 = 1
14! * 2 mod 17 = 16
14! Mod 17 = 8(11) Last Two digits of Number ending in 1
Unit digit will be 1.
Multiply the tens digit of number with the last digit(unit digit) of exponent to get tens digit.Last two digits of 31^786 > 3 * 6 = 18 hence last two digits 81
Last two digits of 41^2789 > 4 * 9 = 36 hence last two digits 61(12) Last two digits of Number ending in 3 or 7 or 9
Try to convert it in to the form of digits ending in 1.
Last two digits of 19^266 = (19^2)^133 = 361^133 => hence last two digits 81
Last two digits of 33^288 = (33^4)^72 = 21^72 > hence last two digits 41
Last two digits of 87^474 = (87^4)^118 * 87^2 = >61^118 * 87^2 => 81*69 =>89(13) Last two digits of Number ending in 2,4,6 or 8
Only one even two digit number which ends in itself(last two digits() is 76.
i.e 76^ any power > last two digits will be 76.
24^2 ends in 76 and 2^10 ends in 24 . 24^even power always ends in 76 and 24^odd power ends with 24.
Last two digits of 2^543 = (2^10)^54 * 2^3 = 24^54 * 2^3 = 76 * 8 => 08
If you multiply 76 with 2^n last two digits will be last two digits of 2^n
64^236 > (2^6)^236 = 2^1516 = (2^10)^151 * 2^6 = 24 * 64 > 36
56^283 = (2^3)^283 * 7^283 = 2^849 * 49^140 *7^3 = (2^10)^84 *2^9 * 01^70 *43 = 76 * 12 *01 * 43 => 16(14) Last two digits of Number ending in 5
There are two cases
 Numbers where previous digit of 5 is 0 or any even number
 Numbers where previous digit of 5 is odd number
In first case if number raised to any power > last two digits 25
In second case if number raised to even power > last two digits 25
In second case if number raised to odd power > last two digits 75.
(15) When both dividend and divisor have a factor in common
Step 1 : Take out the common factor (k)
Step 2 : Divide the resultant dividend by resulting divisor and find out remainder (r)
Step 3 : The real remainder is remainder (r) multiplied by common factor (k)Example : Remainder when 2^96 is divided by 96
96 = 2^5 * 3
2^96 = 2^5 * 2^91 > common term 32
2^91 mod 3 = 2
Remainder = 2*32 = 64(16) Negative remainder
When a number N < D gives a remainder R When divided by D , it gives a negative remainder of RD
Remainder when 7^52 is divided by 2402
7^52 mod 2402 = (7^4 )^13 mod 2402 = 2401^13 mod 2402 = 1^13 = 1
remainder 24021 = 2401(17) Fermat’s Theorem
If P is a prime number and N is co prime to P , Then N^p – N is divisible by P.
(18) Chinese Remainder theorem
If a number N = a * b where HCF (a,b) = 1 and S is a number such that S mod a = r1 and S mod b = r2 then remainder S mod N =ar2x+ br1y where ax+by = 1
A number which when divided by 7,11 and 13 leaves remainder 5, and 8 respectively. IF all such numbers less than 10000 are added what will be the remainder when the sum is divided by 11?
7x+5 = 11y+7 = 13z+8
7x+5 = 11y+7
7x = 11y+2
Solutions are (5,3)(16,10)(27,17)……
Comparing Second and third
11y+7 = 13z+8
11y = 13z+1
solutions are (6,5)(19,16)(32,27)…..
so general form of Y
y = 7a+3 = 13b+6
7a = 13b+3
So numbers of form (6,3),(19,10),(32,17)……
So lowest y = 7 * 6 + 3 = 45
Lowest number = 11 * 45 + 7 = 502
next Y = 19 * 7 + 3 = 136
Next number = 11 * 136 + 7 = 1503
numbers are 502,1503,2504,3505,4506,5507,6508,7509,8510,9511
Sum = 50065
50065 mod 11 = 4(19) Last non zero digit of n!
Z(n) denotes last non zero digit in n!
Z(n) = {4 , if tens digit is odd
6,if tens digit is even } * Z(n/5) * Z(unit digit )Last non zero digit of 36!
Z(36) = 4 * Z(7) * Z(6) = 4 * 4 * 2 = 32. so answer 2Last non zero digit of 15!
Z(15) = 4 * Z(3) * Z(5) = 4 * 6 * 2 > 48 > hence answer 8
(20) Match Sticks Or Coins concept
Suppose two players A and B play a game of coins in which the person picking up the last coin from table wins the game. Let us consider there are 50 coins on a table and a person can pickup maximum 7 coins and minimum one coin of his chance. So if question says A starts the Game what should be the number of coins he must pickup to ensure he wins
If a starts his targets will be 50, 42, 34, 26, 18, 10, 2. So he must pickup two coins to ensure Win.
Suppose in the same question if the player picking up last coin loses the game.
Add minimum and maximum = 1+ 7 = 8
Closest multiple of 8 which is less than 50 is 48. So 5048 = 2If last person who is picking the coin will win , a would have picked 2 . But here he will pick1 so that in the end 1 is left for b. Now whatever b picks up a will match with a number that will make sum 8.
A  B
1  4
4  7
1  7
1  6
2  6
2  5
3  1This is an example and here B is helpless.
(21) To calculate unit digit of A^B
Case 1) When B is not a multiple of 4
B = 4X+Y Where 0 < Y < 4
So here unit digit of A^B will be unit digit of A^YCase 2) When B is a multiple of 4
Even numbers (2,4,6,8) raised to powers which are multiples of 4 give the unit digit as 6
For 1 and 5 ,any power of this will give same unit digit
Other odd numbers (3,7,9) raised to any powers which are multiples of 4 give the unit digit as 1.Unit digit of 9^46
46 = 11*4 + 2
Hence unit digit of 9^46 is same as unit digit of 9^2
hence answer 1Find the unit digit of 7^11^13^17
Here we have to find out whether power is a multiple of 4
so 11^13^17 mod 4 = (121)^13^17 = (1)^13^17 = 1^(odd number) = 1
Hence remainder will be 41 =3
So unit digit of 7^11^13^17 will be same as 7^3 which is 3
(22) Power of a natural number contained in a factorial
Highest power of prime number P In n! = [n/p]+[n/p^2]+[n/p^3]…
where [X] denotes greatest integer less than or equal to XHighest Power of 3 in 50! = [50/3]+[50/9]+[50/27] = 16+5+1 =22
Highest power 30 in 70!
30 = 2 * 3 * 5
Since 5 is the largest prime factor power of 5 will be less than that of 2 and 3.
Hence power of 30 will be equal to power of 5
70/5+70/25 = 14+2 = 16Find the number of zeros present at the end of 90!
Number of zeros present at the end means we have to calculate highest power of 10.
since 10 = 2*5
Highest power of 10 means highest power of 5
90/5+90/25 = 18+3 =21
Hence number of zeros present at the end 21Find the highest power of 24 in 100!
24 = 3 * 2^3
Power of 2 =100/2+100/4+100/8+100/16+100/32+100/64 = 50+25+12+6+3+1 = 97
Power of 2^3 = [97/3] = 32
Power of 3 = 100/3+100/9+100/27+100/81 = 33+11+3+1 = 48
Since power of 2^3 is less , power of 2^3 in 100! Is 32
(23) A number in base N is divisible by N1 when sum of digits of number is in base N is divisible by N1
The number 28A65432 is in base 8. The number is divisible by 7.Then value of A
2+8+A+6+5+4+3+2 = 30+A
30+A mod 7 = 0
A = 5(24) A number has even number of digits in base N , the number is divisible by N+1 if the number is palindrome
A 10 digit palindromic number in base 16 will always be divisible by
Number will be divisible by 17.If n is a natural number find the possible terminating digits of n^2+n is base 5
Terminating digits of n^2+n will be any one of 0, 2, 6.In base 5 this will give 0,
2,1 Remainders respectively. So unit digit of n^2+n in base 5 will be any of 0,1,2.
(25) LCM and HCF
HCF(Highest Common Factor) , It is the largest number that divides two or more given numbers.
LCM(Least Common Multiple), Lowest number which is divisible by all the given numbers.Find HCF and LCM of 288,1080
288 = 2^5 * 3^2
1080 = 2^3 * 3^3 * 5
HCF = 2^3 * 3^2 = 72
LCM = 2^5 * 3^3 * 5(26) The numbers 2604,1020 and 4812 when divided by a number N give the same remainder of 12.Find the highest such number N
Since all the numbers are giving remainder 12, (260412),(102012),(481212) are multiples of N
2592, 1008, 4800
So N will be HCF of 2592,1008 and 4800
2592 = 2^5 * 3^4
1008 = 2^4 * 7 * 3^2
4800 = 2^6 * 5^2 * 3
HCF = 2^4 * 3 = 48(27) The numbers 400,536 and 645 when divided by a number N gave remainders of 22,23 and 24 respectively.Find the greatest such number N
N will be the HCF of (40022),(53623) and (64524)
HCF(378,513,621) = 27(28) The HCF of two numbers is 12 and their sum is 288. How many pairs of such numbers are possible?
Let numbers be 12a, 12b
12(a+b) = 288
a+b = 24 and a and b are co prime
Hence(1,23)(5,19)(7,17)(11,13)
Hence 4 pairs available.(29) HCF of 2 numbers are 12 and their product is 31104. How many such numbers are possible?
Let numbers are 12a n 12b
144ab = 31104
ab = 216
a and b are coprime
(1,216)(8,2)
Only two pairs possible.(30) For two given numbers, HCF * LCM = Product of numbers
(31) If numbers N1, N2 and N3 giving remainders R1, R2 and R3 when divided by the same number P. Then P is the HCF of (N1R1)(N2R2)(N3R3) .
(32) If numbers N1,N2 and N3 give same remainder when divided by same number P then P is a factor of (N1N2) and (N2N3).
(33) Find the Highest five digit number that is divisible by each of the numbers 24, 36, 45 and 60?
LCM (24,36,45,60) => 24 = 2^3 * 3
36 = 3^2 * 2^2
45 = 3^2 * 5
60 = 2^2 * 3 * 5
LCM = 2^3 * 3^2 * 5 = 360
So we have to find highest five digit multiple of 360
99999 mod 360 = 279
so answer 99999279 = 99720(34) Find the lowest number which gives a remainder of 5 when divided by any of the numbers 6,7,8
LCM( 6, 7, 8 ) = 168
number 168 + 5 = 173(35) What is the smallest number which when divided by 9,18 and 24 which leaves a remainder of 5,14 and 20 respectively
LCM(9,18,24) = 72
9  5 = 18  14 = 24  20 = 4
Since difference is same , answer will be LCM – common difference = 724 = 68(36) A number when divided by 3,4,5 and 6 always leave a remainder 2,but leaves no remainder when divided by 7.What is the lowest such number possible?
LCM(3, 4, 5, 6) = 60
Number of the form 60a + 2
60a + 2 = 7b
lowest such number > 182 when a = 3 & b = 26(37) For how many pairs (a,b) of natural numbers is the LCM of a and b 2^3 * 5^7 * 11^13?
Let one of the number contains 2^3
Other may contain 2^0,2^1,2^2,2^3 > 4 possibilities
Number of ordered pairs > 2 * 4 – 1 = 7 (since (2^3,2^3) required only once)
Similarly powers of 5 > 2 * 8 – 1 = 15
Powers of 11> 2 * 14 – 1 = 27
Total 7 * 15 * 27 = 2835(38) An Egyptian fraction has a numerator equal to 1 and its denominator is a positive integer. What is the maximum number of Egyptian fractions such that their sum is equal to 1 and their denominators are equal to 10 or less?
Possible numbers 1/2 ,1/3,1/4,1/5,1/6,1/7,1/8,1/9
Out of which 1/5,1/10,1/7,1/9 can be eliminated since it wont give sum of 1
Similarly 1/4 and 1/8 can be eliminated.
So remaining 1/2, 1/3 and 1/6 = > 1/2 + 1/3 + 1/6 = 1
So maximum number > 3(39) What is the minimum number of square marble tiles required to tile a floor of length 2 meters 56 cm and width 3 m and 36 cm ?
Length = 256 cm
Width = 336 cm
Square side > HCF[256,336] = 16
No of tiles required = 256 * 336/16 * 16 = 336(40) Three containers having 4 ½ , 3 ¼ and 6 1/3 litres of three different cold drinks are to be served equally to all guests in a party such that each one gets maximum. How many maximum number of guests could be entertained ?
HCF [9/2 , 13/4 , 19/3] = 1/12
Maximum number of guests = 9/2 * 12 + 13/4 * 12 + 19/3 * 12 = 54 + 39 + 76 = 169(41) In a book store “OM INNOATIVE BOOK STORE“ is flashed using neon lights. The words are individually flashed at intervals of 2 2/3 , 5 1/3 , 4 2/3 , 7 1/2 seconds respectively and each word is put off after a second . The least time after which the full name of the book store can be read for a second?
At first ON > 8/3 16/3 14/3 15/2
Each word is put off after a second
So Om will flash after > 8/3+1 = 11/3 seconds
Similarly Innovative > 19/3
Book > 17/3
Store > 15/2 + 1 = 17/2
So all will together after LCM [ 11/3 , 19/3, 17/3,17/2] = 11 * 19 * 17 = 3553 SEC(42) If P = 10 * 10! + 11 * 11! + 12 * 12! + … 99 * 99! Then P will end in how many zeros?
P = 10!(111)+11!(121)+……+99!(1001)
= 11!10!+12!11!+13!12!+…..100!99!
= 100!10!
Number of trailing zeros p contain > number of trailing zeros in 10! = 10/5 = 2(43) Let n! = 1 * 2 * 3 … n for integer n > = 1 If P = 1 + ( 2 * 2! ) + ( 3 * 3!) + …. +(12 * 12!). Then P+3 divided by 13! Leaves a remainder of?
n * n! = (n + 1  1) * n! = n!(n+1) – n! = (n+1)!n!
1 * 1! + 2 * 2! + 3 * 3! +…12 * 12! = 2!  1! + 3!  2! + … + 13!  12! = 13!1!
13!  1 + 3 mod 13! = 2 mod 13! =2(44) 64329 is divided by a certain number while dividing the number 175,114 and 213 appear as 3 successive remainders. Divisor is
D  64329
xxx

1752
yyyy

1149
zzzz

213So 643  175 = xxx = 468
1752 – 114 = yyyy = 1638
1149  213 = zzzz = 936
Since D is the factor of all these D = HCF[468,1638,936] = 234(45) For how many integers n is n^4 + 6n < 6n^3 + n^2
n^4+6n < 6n^3+n^2
n^46n^3+6nn^2 < 0
n(n^21)(n6)< 0
n^2 – 1 always positive
So n (n6) is less than 0
n6 less than 0
Possible n values 2,3,4,5(n cant b zero since it will become 0)(46) How many numbers between 1 and 400 both included are not divisible either by 3 or 5?
Multiples of 3 = 3993/3 +1 = 133
Multiples of 5 = 4005/5 +1 = 80
Multiples of 15 = 39015/15 +1 = 26
Multiples of 3 or 5 = 133+8026 = 187
Numbers which are not multiples of 3 or 5 > 400187 = 213(47) Find the remainder when 12345689101112……40 is divided by 36
36 = 4 * 9
123456….40 mod 4 => 40 mod 4 = 0
123456…mod 9
= sum of digits mod 9
= 45 * 3 + 10 * (1+2+3) + 4 mod 9
= 135 + 60 + 4 mod 9 = 199 mod 9 = 1
Hence 4a = 9b+1
Remainder > 28 (a = 7 b = 3)(48) Find the remainder when 1 * 2 + 2 * 3 + 3 * 4 +… 9 * 100 is divided by 101
1 * 2 + 2 * 3 + 3 * 4 + ... 99 * 100 = Sigma[n * (n+1)] From 1 to 99
sigma (n(n+1))
= sigma(n^2+n)
= n(n+1)(2n+1)/6 + n(n+1)/2
= n(n+1)(2n+1)+3n(n+1)/6
= (n+1)/6 * (2n^2+4n)
= 2n(n+1)(n+2)/6
= 198 * 100 * 101/6
198 * 100 * 101/6 mod 101 = 0(49) Find the smallest number with 15 divisors
15 = 3 * 5 = (2+1)(4+1)
so number of the form a^2 * b^4
Smallest number means a = 3 b= 2
3^2 * 2^4 = 9 * 16 = 144(50) How many divisors of 21600 are perfect squares?
21600 = 2^5 * 3^3 * 5^2
The even powers of 2 can be selected in 3 ways
Even powers of 3 can be selected in 2 ways
Even powers of 5 can be selected in 2 waysTotal > 3 * 2 * 2 = 12 divisors are perfect squares
(51) Let N be a composite number such that N = (x)^a * (Y)^b * (Z)^c where X YZ are prime factors.
If N is not a perfect square then number of ways N can be written as a product of two numbers => number of divisors /2(52) If N is a perfect square then number of ways N can be written as a product of two numbers => (number of divisors +1) /2
(53) How many of the first 1200 natural numbers are not divisible by any of 2, 3 and 5?
1200 is a multiple of 2, 3 and 5
Hence we have to find out the number of numbers which are less than and coprime to 1200
1200 * (11/2) * (11/5) * (11/3) [As per Euler]
> 1200 * 1 * 2 * 4/2 * 3 * 5 = 320(54) N is the smallest number such that N/2 is a perfect square and N/3 is a perfect cube. Then the number of divisors of N?
N/2 is a perfect square > power of 2 in N can be 1,3,5….
Power of 3 in N can be 0,2,4…….
N/3 is a perfect cube > power of 2 in N can be 3,6,9….
Power of 3 in N can be 1,4,7…..
Smallest N = 2^3 * 3^ 4
Number of divisors = 4 * 5 = 20

@SiddharthJain Which question/method you found difficult to understand? Let us know so that it will help us improve also. Cheers!

@SiddharthJain Given the scope of CAT it is better not to indulge much in the derivations and proof aspects. Most of the above concepts are basic ones which one need to know and it is better to pick shortcuts ONLY if it can be easily memorized/applied.

 There is a correction another factor would be (8,27).

@RohitRathore HCF of 8 and 27 is not 12.