**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 _{1 }or by + r_{2 }such that ax + r_{1 }= by + r_{2}, 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:

## 3 Responses

19^21 mod 36

18x+1=2y+1

Can we put both x and y 0 and get remainder 1

Actual remainder comes out to be 19

numbers should be co prime

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+1=4y+3

9x=4y+2 ..

By hit and trial Y=4.

So remainder will be 4x+3=19