Bodhee Prep-Online CAT Coaching | Online CAT Preparation | CAT Online Courses

Get 10% OFF on CAT 24 Course. Code: BODHEE10. Valid till 15th May Enroll Now

Chinese Remainder Theorem

Chinese Remainder Theorem:

If a number N = a×b, where a and b are prime to each other, and M is a number such that the remainders obtained when M is divided by a and b are \({r_1}\; and\;{r_2}\) respectively, then the remainder obtained when M is divided by N is the smallest value in the form of ax + r1 or by + r2 such that ax + r1 = by + r2, where x and y are non negative integers.

Solved Example on Chinese remainder theorem for CAT exam

Example:Find the remainder when \({2^{40}}\) is divided by 77.


Observe that3 and 77 are co-prime to each other but \(\phi \left( {77} \right) = \;60\) is less than the 40 (the power of 2). Hence we cannot use Fermat theorem directly to reduce the dividend \({2^{40}}\).

But we can take the help of Chinese Remainder Theorem to get the required remainder.

77 = 7×11, let us divide the dividend \({2^{40}}\) one by one with 7 and 11 to get the respective remainders.

Note that \(\phi \left( 7 \right) = \;6\;and\;\phi \left( {11} \right) = \;10\)

\(\frac{{{2^{40}}}}{{7\;}} = \frac{{{2^{36}} \times {2^4}}}{{7\;}}\)

Note that 36 is multiple of 6 (euler of 7) also 2 and 7 are coprime, hence by Fermat Theorem:

\(\frac{{{2^{36}}}}{{7\;}} \to R\left( 1 \right)\) and \({2^4} = 16\;\) when divided by 7 the remainder obtained is 2.

Therefore, \(\frac{{{2^{40}}}}{{7\;}} \to R\left( 2 \right)\)

Similarly, \(\frac{{{2^{40}}}}{{11\;}} \to R\left( 1 \right)\)

Now, according to Chinese Remainder Theorem, the final remainder is in the form of 7x +2 or 11y +1.

Equating both to get the smallest solution we get,

7x +2 = 11y + 1

Or 7x + 1 = 11y

With some hit and trial, we get x = 3 and y = 2. And the Final remainder is 7x+2 = 7*3+2 =23.

you may also like:

How to find last two digits

3 Responses

  1. 19^21 mod 36
    Can we put both x and y 0 and get remainder 1
    Actual remainder comes out to be 19

  2. The factor of divisor must be co-prime .
    Break 36 into 9*4.
    19^21/9 will give you remainder =1
    19^21/4 will give remainder =-1= 3
    So remainder would be in the form of.
    9x+1 or 4y+3
    9x=4y+2 ..
    By hit and trial Y=4.
    So remainder will be 4x+3=19

Leave a Reply

Your email address will not be published. Required fields are marked *

CAT Online Courses

FREE CAT Prep Whatsapp Group

CAT 2024 Online Course at affordable price