Collection of Number Theory Concepts - Maneesh


  • Converted IIM Indore call | Mentor for Banking/RBI/SSC exams


    (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)/(b-1) * ((c^(p+1) -1 )/(c-1)

    Find the sum of divisors of 120
    120 = 2^3 * 3 * 5
    sum = 2^4 – 1 / 1 * 3^2-1/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^(m-1) 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 12

    Number 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^(m-1)+3^(m-2) +…. + 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(1-1/2) ( 1-1/5)

    In general a positive integer N having prime divisors p1, p2, p3 … pn
    E[N] = N(1-1/p1)(1-1/p2) ... (1-1/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, (P-1)! +1 is divisible by P
    (P-1)! Mod P = -1 or (P-1)
    (P-2)! Mod P = 1
    (p-3)! Mod P = (p-1)/2

    16! = (16!+1)-1 = (16!+1)+16-17
    16! Mod 17 = 0 + 16 - 0 = 16

    15! Mod 17 => 16!mod 17 = 16
    15! * 16 mod 17 = 16
    15! Mod 17 =1

    14! 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

    1. Numbers where previous digit of 5 is 0 or any even number
    2. 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 R-D

    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 2402-1 = 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 )

    1. Last non zero digit of 36!
      Z(36) = 4 * Z(7) * Z(6) = 4 * 4 * 2 = 32. so answer 2

    2. Last 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 pick-up 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 pick-up to ensure he wins

    If a starts his targets will be 50, 42, 34, 26, 18, 10, 2. So he must pick-up 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 50-48 = 2

    If 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 ------ 1

    This 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^Y

    Case 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.

    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 1

    2. Find 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 = (12-1)^13^17 = (-1)^13^17 = -1^(odd number) = -1
      Hence remainder will be 4-1 =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 X

    1. Highest Power of 3 in 50! = [50/3]+[50/9]+[50/27] = 16+5+1 =22

    2. 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 = 16

    3. Find 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 21

    4. Find 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 N-1 when sum of digits of number is in base N is divisible by N-1

    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

    1. A 10 digit palindromic number in base 16 will always be divisible by
      Number will be divisible by 17.

    2. 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, (2604-12),(1020-12),(4812-12) 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 (400-22),(536-23) and (645-24)
    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 (N1-R1)(N2-R2)(N3-R3) .

    (32) If numbers N1,N2 and N3 give same remainder when divided by same number P then P is a factor of (N1-N2) and (N2-N3).

    (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 99999-279 = 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 = 72-4 = 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!(11-1)+11!(12-1)+……+99!(100-1)
    = 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
    --------
    213

    So 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^4-6n^3+6n-n^2 < 0
    n(n^2-1)(n-6)< 0
    n^2 – 1 always positive
    So n (n-6) is less than 0
    n-6 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 = 399-3/3 +1 = 133
    Multiples of 5 = 400-5/5 +1 = 80
    Multiples of 15 = 390-15/15 +1 = 26
    Multiples of 3 or 5 = 133+80-26 = 187
    Numbers which are not multiples of 3 or 5 -> 400-187 = 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 ways

    Total -> 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 * (1-1/2) * (1-1/5) * (1-1/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


  • Being MBAtious!


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


  • Being MBAtious!


    @Siddharth-Jain 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 short-cuts ONLY if it can be easily memorized/applied.



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

  • administrators

    @Rohit-Rathore HCF of 8 and 27 is not 12.


Log in to reply
 

Looks like your connection to MBAtious was lost, please wait while we try to reconnect.