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.

Solution:

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


Try CAT 2020 online course for 1 day for FREE

Please provide your details to get FREE Trial of Bodhee Prep's Online CAT Course for one day. We will inform you about the trial on your whatsApp number with the activation code.

Leave a Reply

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