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