Remainder Theorem and related concepts for CAT Preparation - Ravi Handa


  • www.handakafunda.com | IIT Kharagpur


    Are you struggling with Remainders?
    Here is a bunch of questions with detail solutions.

    Fermat's Theorem : Rem [a^(p-1)/p] = 1, where p is a prime number and HCF(a, p) = 1

    What is the remainder of 57^67^77/17 ?

    Rem [57^67^77/ 17] = Rem [6^67^77/17]
    Now, by Fermat's theorem, we know Rem [6^16/17] = 1
    The number given to us is 6^67^77
    Let us find out Rem[Power / Cyclicity] to find out if it 6^(16k+1) or 6^(16k+2).
    We can just look at it and say that it is not 6^16k

    Rem [67^77/16] = Rem [3^77/16]
    = Rem[(3^76*3^1)/16]
    = Rem[((81^19) * 3)/16]
    = Rem [1 * 3/16]
    = 3

    => The number is of the format 6^(16k + 3)
    => Rem [6^67^77 /17]
    = Rem [6^(16k + 3)/17]
    = Rem [6^3/17]
    = Rem [216/17] = 12

    What is the remainder when 2^1000 is divided by 59?

    We have to find out Rem [2^1000/59]
    As per Fermat's Theorem, [a^(p-1)/p] = 1 where p is a prime number and HCF(a,p) = 1

    Rem [2^58 / 59] = 1
    => Rem [(2^58)^17 / 59] = 1
    => Rem [2^986 / 59] = 1

    Rem [2^1000/59]
    = Rem [2^986 x 2^14 / 59]
    = Rem [1 x 128 x 128 / 59]
    = Rem [1 x 10 x 10 / 59]
    = Rem [100/59]
    = 41

    What is the remainder when 2^89 is divided by 89?

    We can use Fermat's Theorem here which says
    Rem [a^(p-1)/p] = 1 where p is a prime number
    => Rem [2^88/89] = 1
    => Rem [2^89/89] = Rem [2^88/89] * Rem [2/89] = 1 * 2 = 2

    What is the remainder when 17^432 is divided by 109?

    As per Fermat's Theorem, [a^(p-1)/p] = 1 where p is a prime number and HCF(a,p) = 1
    Rem [17^108 / 109] = 1
    => Rem [(17^108)^4 / 109] = 1
    => Rem [17^432 / 109] = 1

    What is the remainder when 17^325 is divided by 109?

    As per Fermat's Theorem, [a^(p-1)/p] = 1 where p is a prime number and HCF(a,p) = 1
    Rem [17^108 / 109] = 1
    => Rem [(17^108)^3 / 109] = 1
    => Rem [17^324 / 109] = 1
    => Rem [17^324 * 17 / 109] = 1*17
    => Rem [17^325 / 109] = 17

    What is the remainder when 2^1040 is divided by 131?

    As per Fermat's Theorem, [a^(p-1)/p] = 1 where p is a prime number and HCF(a,p) = 1
    Rem [2^130 / 131] = 1
    => Rem [(2^130)^8 / 131] = 1
    => Rem [2^1040 / 131] = 1

    Euler's Theorem

    What is the remainder of (121) ^(121) divided by 144?

    Euler Totient (144) = 144*(1-1/2)(1-1/3) = 48
    By Euler's Theorem we can say that
    Rem[a^48/144] = 1 if a and 144 are coprime to each other
    => Rem [a^240/144] = 1
    => Rem [11^240/144] = 1

    Now, we need to find out Rem [121^121/144]
    = Rem [11^242/144]
    = Rem [11^240/144] * Rem [11^2/144]
    = 1 * 121
    = 121

    Wilson's Theorem

    Wilson's Theorem says For a prime number 'p', Rem [ (p-1)! / p] = p-1
    This can be extended to say, Rem [ (p-2)! / p] = 1

    What is the remainder when 97! is divided by 101?

    We need to find out Rem [97! / 101] = r
    We know from the above theorem,
    Rem [99! / 101] = 1
    => Rem [99 * 98 * 97! / 101] = 1
    => Rem [ (-2)*(-3)*r / 101] = 1
    => Rem [6r / 101] = 1
    => 6r = 101k + 1
    We need to think of a value of k, such that 101k + 1 is divisible by 6.
    If we put, k = 1, we get 101 + 1 = 102, which is divisible by 6.
    => 6r = 102
    => r = 17

    What is the remainder when 21! is divided by 361?

    Rem [21!/361]
    = Rem [(21 * 20 * 19 * 18!)/361]
    Using Rem [ka/kb] = k Rem[a/b]
    = 19 Rem [(21 * 20 * 18!)/19]
    Using Wilson's Theorem says For a prime number 'p' Rem [ (p-1)! / p] = p-1
    = 19 Rem [(21 * 20 * 18)/19]
    = 19 Rem [(2 * 1 * (-1))/19]
    = 19 * (-2)
    = -38
    = 323

    Pattern Recognition / Cyclicity Method

    What is the remainder when 7^99 is divided by 2400?

    Let us try doing it by the pattern recognition / cyclicity method. It can be really long if you do not get the pattern quickly. Use other methods like Euler's Totient if you do not get a pattern quickly.

    Rem[7^1 / 2400] = Rem [7 / 2400] =7
    Rem[7^2 / 2400] = Rem [49 / 2400] =49
    Rem[7^3 / 2400] = Rem [343/ 2400] = 343
    Rem[7^4 / 2400] = Rem [2401 / 2400] = 1

    After this the same pattern will keep on repeating because you got a 1.
    Once we have obtained the cyclicity (number of terms in the pattern), all we need to do is to find out the Remainder of Power when divided by the Cyclicity. Whatever is this remainder, that particular value in the cycle is our answer.
    In this case, power is 99 and cyclicity is 4.
    Rem [Power / Cyclicity] = Rem [99/4] = 3
    => Our answer will be the third value in the cycle = 343

    What is the remainder when 32^32^32 is divided by 7?

    Rem [32^32^32 / 7] = Rem [4^32^32 /7]

    Now, we need to observe the pattern
    4^1 when divided by 7, leaves a remainder of 4
    4^2 when divided by 7, leaves a remainder of 2
    4^3 when divided by 7, leaves a remainder of 1

    And then the same cycle of 4, 2, and 1 will continue.
    If a number is of the format of 4^(3k+1), it will leave a remainder of 4
    If a number is of the format of 4^(3k+2), it will leave a remainder of 2
    If a number is of the format of 4^(3k), it will leave a remainder of 1

    The number given to us is 4^32^32

    Let us find out Rem[Power/Cyclicity] t0 find out if it 4^(3k+1) or 4^(3k+2). We can just look at it and say that it is not 4^3k

    Rem [32^32/3] = Rem [(-1)^32/3] = 1
    => The number is of the format 4^(3k + 1)
    => Rem [4^32^32 /7] = 4

    What is the remainder when 32^ (32^ (32^...infinite times)) is divided by 9?

    Rem [32^32^32... / 9] = Rem [4^32^32... /9]

    Now, we need to observe the pattern
    4^1 when divided by 9, leaves a remainder of 4
    4^2 when divided by 9, leaves a remainder of 7
    4^3 when divided by 9, leaves a remainder of 1

    And then the same cycle of 4, 7, and 1 will continue.
    If a number is of the format of 4^(3k+1), it will leave a remainder of 4
    If a number is of the format of 4^(3k+2), it will leave a remainder of 7
    If a number is of the format of 4^(3k), it will leave a remainder of 1

    The number given to us is 4^32^32....

    Let us find out Rem[Power/Cyclicity] to find out if it 4^(3k+1) or 4^(3k+2). We can just look at it and say that it is not 4^3k

    Rem [32^32^32.../3] = Rem [(-1)^32^32.../3] = 1
    => The number is of the format 4^(3k + 1)
    => Rem [4^32^32 /9] = 4

    What is the remainder when 34^31^301 is divided by 9?

    Rem [34^31^301 / 9] = Rem [7^31^301 /9]

    Now, we need to observe the pattern
    7^1 when divided by 9, leaves a remainder of 7
    7^2 when divided by 9, leaves a remainder of 4
    7^3 when divided by 9, leaves a remainder of 1
    And then the same cycle of 7, 4, and 1 will continue.
    If a number is of the format of 7^(3k+1), it will leave a remainder of 7
    If a number is of the format of 7^(3k+2), it will leave a remainder of 4
    If a number is of the format of 7^(3k), it will leave a remainder of 1

    The number given to us is 7^31^301
    Let us find out Rem[Power/Cyclicity] to find out if it 7^(3k+1) or 7^(3k+2). We can just look at it and say that it is not 7^3k
    Rem [31^301/3] = Rem [1^301/3] = 1
    => The number is of the format 7^(3k + 1)
    => Rem [7^31^301 /9] = 7

    What is the remainder of 30^72^87 when divided by 11?

    Rem [30^72^87 / 11] = Rem [(-3)^72^87 / 11] = Rem [3^72^87 / 11]

    Now, we need to observe the pattern
    3^1 when divided by 11, leaves a remainder of 3
    3^2 when divided by 11, leaves a remainder of 9
    3^3 when divided by 11, leaves a remainder of 5
    3^4 when divided by 11, leaves a remainder of 4
    3^5 when divided by 11, leaves a remainder of 1
    And then the same cycle of 3, 9, 5, 4 and 1 will continue.
    If a number is of the format of 3^(5k + 1), it will leave a remainder of 3
    If a number is of the format of 3^(5k + 2), it will leave a remainder of 9
    If a number is of the format of 3^(5k + 3), it will leave a remainder of 5
    If a number is of the format of 3^(5k + 4), it will leave a remainder of 4
    If a number is of the format of 3^(5k), it will leave a remainder of 1

    The number given to us is 3^72^87
    Let us find out Rem[Power/Cyclicity] to find out if it 3^(5k + what?)

    Rem [72^87 / 5]
    = Rem [2^87 / 5]
    = Rem [2 * 4^43/5]
    = Rem [2 * (-1) / 5]
    = -2
    = 3
    => The number is of the format 3^(5k + 3)
    => Rem [3^72^87 / 11] = 5

    What is the remainder when 1! +2 * 2! + 3 * 3! + 4 * 4! +... +12 * 12! Is divided by 13?

    The trick in these type of questions is often observing the pattern
    1! + 2 * 2! = 1 + 4 = 5 = 3! - 1
    1! + 2 * 2! + 3 * 3! = 1 + 4 + 18 = 23 = 4! - 1
    1! + 2 * 2! + 3 * 3! + 4 * 4! = 1 + 4 + 18 + 96 = 119 = 5! - 1
    1! + 2 * 2! + 3 * 3! + 4 * 4! + 5 * 5! = 1 + 4 + 18 + 96 + 600 = 719 = 6! - 1
    So, we can say
    1! + 2 * 2! + 3 * 3! + 4 * 4! +... + 12 * 12! = 13! - 1
    => Rem [(1! + 2 * 2! + 3 * 3! + 4 * 4! +... + 12 * 12!) / 13] = -1 = 12

    What is the remainder of 57^67^77/17 ?

    Rem [57^67^77/ 17] = Rem [6^67^77/17]

    Now, by Fermat's theorem, which states Rem [a^(p-1)/p] = 1, we know
    Rem [6^16/17] = 1

    The number given to us is 6^67^77
    Let us find out Rem[Power/Cyclicity] to find out if it 6^(16k+1) or 6^(16k+2). We can just look at it and say that it is not 6^16k
    Rem [67^77/16] = Rem [3^77/16] = Rem[(3^76 * 3^1)/16]
    = Rem[((81^19) * 3)/16] = Rem [1 * 3/16] = 3

    => The number is of the format 6^(16k + 3)

    => Rem [6^67^77 /17] = Rem [6^(16k + 3)/17] = Rem [6^3/17]
    = Rem [216/17] = 12

    How do you find the remainder when 7^26 is divided by 100?

    Finding out the remainder from 100, is the same as finding out the last two digits of a number
    Last two digits of 7^1 are 07
    Last two digits of 7^2 are 49
    Last two digits of 7^3 are 43
    Last two digits of 7^4 are 01
    After this, the same pattern will keep on repeating.
    So, 7^(4n+1) will end in 07, 7^(4n+2) will end in 49, 7^(4n + 3) will end in 43, and 7^4n will end in 01

    7^26 = 7^(4n+2) will end in 49
    => Rem [7^26/100] = 49

    Using Binomial Theorem

    What is the remainder when 25^10 is divided by 576?

    We need to find out the remainder of 25^10 when divided by 576.
    Please note that 576 = 24^2

    25^10 = (24 + 1)^10

    In the expansion, there will be 11 terms where the powers of 24 will vary from 0 to 10.
    If the power of 24 is greater than or equal to 2 in a term, that term will be divisible by 576
    The terms that will not be divisible by 576 are the terms that have powers of 24 as 0 or 1.
    Those terms are
    10C1 * 24^1 * 1^9 + 10C0 * 24^0 * 1^10
    = 10 * 24 * 1 + 1 * 1 * 1
    = 241
    So, Rem [25^10/576] = 241

    Finding Remainders by Simplifying the Dividend

    Type 1: Simplifying the dividend (Direct)

    What's the remainder when 2^99 is divided by 33?

    To solve these kind of questions, it is important that we modify the dividend. We should break it in such a format that it gets close to the divisor - preferably +1 or -1 of the divisor. For example, in this question we are dividing the numerator by 33. We should try to make the numerator 32 or 34. Since it is powers of 2, making it 32 is possible.

    Let's have a look at the complete and detailed solution below.

    Rem [2^99 / 33]
    = Rem [2^4 * 2^95 / 33]
    = Rem [16 * 32^19 / 33]
    = Rem [16 * (-1)^19 / 33]
    = Rem [ (-16) / 33]
    = 17

    What is the remainder when 17^200 is divided by 18?

    These type of questions become really simple if you understand the concept of negative remainders. Always try and reduce the dividend to 1 or -1.
    Rem [17^200 / 18]
    = Rem [ (-1)^200 / 18]
    = Rem [1 / 18]
    = 1

    What is the remainder when 30^100 is divided by 17?

    Rem [30^100 / 17]
    = Rem[(-4)^100 / 17]
    = Rem[16^50/ 17]
    = Rem[(-1)^50 / 17]
    = Rem[1^50 / 17]
    = 1

    How do you find the remainder of 54^124 divided by 17?

    Rem [54^124 / 17]
    = Rem[(3)^124 / 17]
    = Rem[81^31 / 17]
    = Rem[(-4)^31 / 17]
    = Rem[(-4)^30 * (-4) / 17]
    = Rem[(16)^15 * (-4) / 17]
    = Rem[(-1)^15 * (-4) / 17]
    = Rem[(-1) * (-4) / 17]
    = 4

    How do you find the remainder of 21^875 divided by 17?

    Rem [21^875 / 17]
    = Rem [4^875 / 17]
    = Rem[4 * 4^874 / 17]
    = Rem [4 * 16^437 / 17]
    = Rem [4 * (-1)^437 / 17]
    = Rem [4 * (-1) / 17]
    = Rem [-4 / 17]
    = 13

    What will be the remainder when (16^27+37) is divided by 17?

    Rem [(16^27+37)/17]
    = Rem [16^27/17] + Rem [37/17]
    = Rem [(-1)^27/17] + 3
    = -1 + 3
    = 2

    What is the remainder when 2^33 is divided by 27?

    Rem [2^33/27]
    = Rem [32^6 * 8 / 27]
    = Rem [5^6 * 8 / 27]
    = Rem [ 125^2 * 8 / 27]
    = Rem [ (-10)^2 * 8 / 27]
    = Rem [800/27]
    = 17

    What is the remainder of the following question (71^71+71) / (72)?

    Rem [(71^71 + 71)/72]
    = Rem [71^71/72] + Rem [71/72]
    = Rem [(-1)^72] + (-1)
    = (-1) + (-1)
    = -2
    = 70

    How will you find the remainder when 15^2010+16^2011 is divided by 7?

    Here we need to know that:
    Rem[(a + b)/c] = Rem[a/c] + Rem[b/c]
    Rem[(a*b)/c] = Rem[a/c] * Rem[b/c]

    Keeping that in mind:
    Rem[15^2010/7] = Rem[1^2010/7] = 1

    Rem[16^2011/7]
    = Rem[2^2011/7]
    = Rem[2^2010/7] * Rem[2/7]
    = Rem[8^670/7] * 2
    = 1 * 2 = 2
    Rem[(15^2010 + 16^2011)/7] = 1 + 2 = 3

    What is the remainder when 30^40 is divided by 7?

    Rem [30^40 / 7]
    = Rem[2^40 / 7]
    = Rem[2^39 * 2 / 7]
    = Rem[8^13 * 2 / 7]
    = Rem[1^13 * 2 / 7]
    = Rem[1*2 / 7]
    = 2

    Solve for the remainder of (19^98)/7?

    Rem [19^98/7]
    = Rem [(-2)^98/7]
    = Rem [2^98/7]
    = Rem [ 2^96 * 2^2 / 7]
    = Rem [ 8^32 * 4 / 7]
    = Rem [1 * 4 / 7]
    = 4

    What is the remainder when 7^2015 is divided by 9?

    Rem [7^2015 / 9]
    = Rem [(-2)^2015 / 9]
    = Rem [ 4 * (-2)^2013 / 9]
    = Rem [ 4 * (-8)^671 / 9]
    = Rem [ 4 * 1 / 9]
    = 4

    What is the remainder when 2014^2015 is divided by 9?

    Rem [2014^2015 / 9]
    = Rem [(-2)^2015 / 9]
    = Rem [ 4 * (-2)^2013 / 9]
    = Rem [ 4 * (-8)^671 / 9]
    = Rem [ 4 * 1 / 9]
    = 4

    What is the remainder when 2^2003 is divided by 17?

    Rem [2^2003 / 17]
    = Rem [2^2000 * 8 /17]
    = Rem [16^500 * 8 / 17]
    = Rem [(-1)^500 * 8 / 17]
    = Rem [ 1*8/17]
    = 8

    What is the remainder if 7^121 is divided by 17?

    Rem [7^121 / 17]
    = Rem [7^120 * 7 / 17]
    = Rem [49^60 * 7 / 17]
    = Rem [(-2)^60 * 7 / 17]
    = Rem [ 16^15 * 7 /17]
    = Rem [ (-1)^15 * 7 / 17]
    = Rem [ (-7) / 17]
    = 10

    Type 2: Simplifying the dividend (Multiple divisors)

    What is the remainder of 2^90/91?

    This looks a little difficult if you do not any theorems for finding out remainders. Let us take a simpler approach and break down the problem into smaller parts.

    These type of questions become really simple if you understand the concept of negative remainders. Always try and reduce the dividend to 1 or -1.

    91 = 7 * 13

    Let us find out Rem[2^90/7] and Rem[2^90/13]
    We will combine them later.

    Rem [2^90/7]
    = Rem [ (2^3)^30 / 7]
    = Rem [ 8^30 / 7]
    = Rem [1^30 / 7]
    = 1

    Rem [2^90/13]
    = Rem [ (2^6)^15 / 13]
    = Rem [ 64^15 / 13]
    = Rem [ (-1)^15 / 13]
    = -1 from 13
    = 12

    So, our answer is a number which leaves a remainder of 1 when divided by 7 and it should leave a remainder of 12 when divided by 13.

    Let us start considering all numbers that leave a remainder of 12 when divided by 13
    => 12 (leaves a remainder of 5 from 7. Invalid)
    => 25 (leaves a remainder of 4 from 7. Invalid)
    => 38 (leaves a remainder of 3 from 7. Invalid)
    => 51 (leaves a remainder of 2 from 7. Invalid)
    => 64 (leaves a remainder of 1 from 7. Valid. This is our answer)

    What is the remainder when 128^1000 is divided by 153?

    153 = 9*17
    128^1000 = 2^7000

    Let us find out Rem[2^7000/9] and Rem[2^7000/17]
    We will combine them later.

    Rem[2^7000/9]
    = Rem [ 2^6999 x 2 / 9]
    = Rem [ 8^2333 x 2 / 9]
    = Rem [ (-1)^2333 x 2 / 9]
    = Rem [ (-1) x 2 / 9]
    = - 2 from 9
    = 7

    Rem[2^7000/17]
    = Rem [16^1750 / 17]
    = Rem [ (-1)^1750 / 17]
    = 1

    So, our answer is a number which leaves a remainder of 7 when divided by 9 and it should leave a remainder of 1 when divided by 17.

    Let us start considering all numbers that leave a remainder of 1 when divided by 17
    => 18 (leaves a remainder of 0 from 9. Invalid)
    => 35 (leaves a remainder of 8 from 9. Invalid)
    => 52 (leaves a remainder of 7 from 9. Valid. This is our answer)

    What is the remainder when 15^40 divided by 1309?

    1309 = 7 * 11 * 17

    Let us find out Rem[15^40/7], Rem[15^40/11] , and Rem[15^40/17]
    We will combine them later.

    Rem[15^40/7]
    = Rem [1^40/7]
    = 1

    Rem[15^40/11]
    = Rem [4^40/11]
    = Rem [256^10/11]
    = Rem [3^10/11]
    = Rem [243^2/11]
    = Rem [1^2/11]
    = 1

    Rem[15^40/17]
    = Rem [(-2)^40/17]
    = Rem [16^10/17]
    = Rem [(-1)^10/17]
    = 1

    So, our answer is a number which leaves a remainder of 1 when divided by 7, 11, and 17
    Such a number is 1 itself and that is our answer.

    Type: Taking values common from Dividend and Divisor

    What is the remainder of the value 39 to the power 198 divided by 12?

    Rem [39^198 / 12]
    = Rem [3^198 / 12]
    = 3 * Rem[3^197 / 4]
    = 3 * Rem[(-1)^197 / 4]
    = 3 * Rem[-1 / 4]
    = 3 * 3
    = 9

    What is the remainder when 3^164 is divided by 162?

    To solve this, you need to know that Rem [ka/kb] = k Rem[a/b]

    We need to find out
    Rem [3^164/162]
    = Rem [(3^4 x 3^160) / (3^4 x 2)]
    = 3^4 Rem [3^160/2]
    = 3^4 Rem [1^160/2]
    = 3^4 x 1
    = 81

    What is the remainder when 21! is divided by 361?

    Rem [21!/361]
    = Rem [(21 * 20 * 19 * 18!)/361]
    Using Rem [ka/kb] = k Rem[a/b]
    = 19 Rem [(21 * 20 * 18!)/19]

    Using Wilson's Theorem says For a prime number 'p' Rem [ (p-1)! / p] = p-1
    = 19 Rem [(21 * 20 * 18)/19]
    = 19 Rem [(2 * 1 * (-1))/19]
    = 19 * (-2)
    = -38
    = 323

    What is the remainder when 2(8!)-21(6!) divides 14(7!) +14(13!)?

    We need to find out Rem [(14(7!) + 14(13!)) / (2(8!) - 21(6!)) ]
    Let us try and simplify the divisor
    2(8!) - 21(6!)
    = 2 * 8 * 7! - 3 * 7 * 6!
    = 16 * 7! - 3 * 7!
    = 13 * 7!

    Rem [(14(7!) + 14(13!)) / 13*7! ]
    = Rem [14(7!) / 13(7!)] + Rem [14(13!) / 13(7!)]
    = 7! * Rem[14/13] + 0
    = 7! * 1
    = 7!


 

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