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 + r₁ or by + r₂ such that ax + r₁ = by + r₂, 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