Gyan Room - Number Theory - Concepts & Shortcuts



  • Gyan Room - There's always room to learn more!
    This thread is reserved for sharing concepts, short cuts and good questions from Number Theory topic.

    0_1502944041457_MissionIIMpossible.png

    Happy Learning, Stay MBAtious!


  • Being MBAtious!


    Concept: f(x) = x^1/x is maximum at x = e ( e = 2.71) and f(x) will decrease if you go either side of x = e

    We can use the same trick to compare a^b and b^a
    Closer the base (a or b) is to e, higher the value will be.

    example:
    9.1 ^ 8.9 and 8.9 ^ 9.1
    both these values are greater than e, and 8.9 is closer to e than 9.1, so 8.9^9.1 is higher than 9.1^8.9

    another classic one,
    which is greater, e^PI or PI^e ?
    we know e = 2.7 and PI = 3.14 => e^PI is greater.

    This trick is especially handy when all the given numbers belongs to the same side of e, where we can do the comparison in no time.


  • Being MBAtious!


    Number of ordered pairs possible for LCM = N = P1^a x P2^b x P3^c
    = [ (a+1)^2 - a^2] [b+1)^2 - b^2] [ (c+1)^2 - c^2]
    = (2a + 1 ) ( 2b + 1) (2c + 1)
    Where, a, b and c are power of prime factors

    Example - If LCM of two numbers is 360, how many such ordered pairs are possible?

    360 = 2^3 * 3^2 * 5
    so our formula is (2a + 1)(2b + 1)(2c + 1)
    where a , b and c are power of prime
    So [(2 * 3 + 1)(2 * 2 + 1)(2 * 1 + 1)
    7 * 5 * 3 = 105


  • Being MBAtious!


    To find LCM and HCF of (a/b) and (c/d) the generalized formula will be:
    H.C.F = H.C.F of numerators / L.C.M of denominators
    L.C.M = L.C.M of numerators / H.C.F of denominators

    a x b = HCF (a, b) x LCM (a, b)

    If a and b are co primes then HCF (a, b) = 1
    So for co prime numbers, a x b = LCM (a, b)


  • QA/DILR Mentor | Be Legend


    How many ways can you express 360 as product of 2 co-primes

    Unordered : 2^(n-1)
    Ordered : 2^n

    How many factor pairs of 360 exist which are co-primes to each other

    Let me explain the concept of factor pair with a small example.
    let say you need co-prime factor pairs of 10. then what would be the answer?
    (1,1), (1,2) ,(1,5), (1,10) , (2,5) ..
    now lets decipher n generalize it

    Factor Pairs of a number x = 2^m * 3^n * .....
    Case - 1 (1,1 ) --> 1
    Case -2 = ; (1,2^m) ; (1,3^n) ; (As HCF should be 1)
    total arrangements = 2(m+n)
    case - 3 = (1,2^m*3^n) (As HCF should be 1)
    total arrangements = 2 * m * n
    Case - 4 (2^m , 3^n) (HCF = 1)
    total arrangements = 2 * m * n
    So total ordered cases for factor pairs = 1 + 2(m + n) + 4mn = (2m + 1) * (2n + 1)
    this is the general formula for factor pairs (ordered )

    in case of x = 360
    360 = 2^3 * 3^2 * 5
    Ordered factor pairs = (2 * 3 + 1) * (2 * 2 + 1) * (2 * 1+ 1 ) = 105


  • NMIMS, Mumbai (Marketing)


    Useful Tip :

    If N is a natural number, number of natural numbers in the range :
    Case 1 : A < = N < = B
    Number of natural numbers in the range : (B - A) + 1
    Case 2 : A < = N < B OR A < N < = B
    Number of natural numbers in the range : (B - A)
    Case 3 : A < N < B
    Number of natural numbers in the range : (B - A) - 1

    Practice examples :
    Q1) How many numbers,N, in the range :
    a) 100 < = N < = 200 b) 100 < = N < 200 c) 100 < N < 200
    Q2) How many even numbers,N, in the range :
    a) 100 < = N < = 250 b) 120 < = N < 360
    Q3) How many numbers,N, of the form 3k,where k is any positive integer in the range :
    a) 50 < N < 300 b) 100 < = N < 500 c) 100 < = N < = 1000

    Should help at a lot of places. So practice well if you are starting your preparations.


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


    How to find the Number of digits in a^b ?

    Number of digits in a^b = [1 + log (a^b)]
    Here [x] denotes the Greatest Integer Function
    We will calculate the value of log(a^b) in base 10

    Example : What is the number of digits in 35^29
    Solution: [ 1+ log 10 (35^29) ]
    = [ 1+ 29 log 10 (35) ]
    = [ 1+ 29 * 1.54 ]
    = [ 1+ 44.776 ]
    = [ 45.776 ]
    = 45 digits


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


    Perfect Squares :

    If the unit digit of a perfect square is 1, the “tens” digit must be even. Example : 1^2 = 01, 9^2 = 81, 11^2 = 121
    If the unit digit of the perfect square is 5, then the tens digit must be 2.
    If the Unit digit of a perfect square is 6, then the tens digit must be “odd”
    The number of zeroes present at the end of any perfect square cannot be “odd”. They must be in the form of 2k, where k =0,1,2,3…..
    A perfect Square of the form “aabb” is 7744 ( 88^2 = 7744 )


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


    Factors :

    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

    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

    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)}

    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


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


    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)

    Examples :

    (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


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


    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.


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


    Remainder theorem :

    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 positive 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

    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]

    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

    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

    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

    Fermat’s Theorem

    If P is a prime number and N is co prime to P , Then N^p – N is divisible by P.

    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


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


    Finding Digit(s) :

    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

    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

    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

    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.

    Last non zero digit of n!

    Z(n) denotes last non zero digit in n!
    Z(n) = 4 * Z(n/5) * Z (unit digit), if ten's digit is odd
    = 6 * Z(n/5) * Z (unit digit), if tens digit is even

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

    Last non zero digit of 15!
    Z(15) = 4 * Z(3) * Z(5) = 4 * 6 * 2 -> 48. hence answer 8

    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.

    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

    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


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


    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

    Highest 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 = 16

    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

    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


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


    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

    Example : 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

    A number has even number of digits in base N, the number is divisible by N + 1 if the number is palindrome

    For two given numbers, HCF * LCM = Product of numbers

    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)

    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)

    Let N be a composite number such that N = (x)^a * (y)^b * (z)^c where x, y and z are prime factors.
    a) 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
    b) 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


Log in to reply
 

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