# 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

### 3 thoughts on “Chinese Remainder Theorem”

1. 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

1. numbers should be co prime

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+1=4y+3
9x=4y+2 ..
By hit and trial Y=4.
So remainder will be 4x+3=19

### CAT 2021 Crash Course + Mock Test Series (INR 4999 Only)

• 50 Live Sessions
• 1000+ Practice problems
• 30 Sectional Tests
• 15 CAT Mock Tests (Video Solutions)
• Dedicated Whatsapp group for doubt clearing
• Valid till 31st March 2022
 Bodhee Prep's YouTube channel CAT Prep Whatsapp Group CAT Prep Telegram Group X
 CAT prep Telegram Group