Bodhee Prep-Online CAT Coaching | Online CAT Preparation | CAT Online Courses

15% OFF on all CAT Courses. Discount code: BODHEE015. Valid till 7th Feb Enroll Now
| Best Online CAT PreparationFor Enquiry CALL @ +91-95189-40261

# 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 Responses

1. Sunny says:

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. navratanrathi123 says:

numbers should be co prime

2. Sulabh tiwari says:

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

### [PDF] CAT 2021 Question Paper (slot 1, 2 & 3) with Solutions

CAT 2021 question paper PDF is available on this page. The page has the CAT 2021 question paper PDFs of all the three slots. There

### All About CAT Mock Test Series

Table of Content for CAT Mock Tests Ideal number of CAT Mock Test Series How many CAT mocks should one write What is the right

### [PDF] CAT 2020 Question Paper (slot 1,2 &3) with Solution

CAT 2020 question paper threw a number of surprises. Not only was there a change in exam pattern but also the difficulty level of almost

##### CAT Online Courses
FREE CAT prep Whatsapp Group