# Thread: Need help understanding the Chinese Remainder Theorem

1. ## Need help understanding the Chinese Remainder Theorem

Here is a simple example.

x 11 (mod 39)
x 7 (mod 22)

I would greatly appreciate it if someone could explain how to do this. I know first of all that 39a+22b=1. I believe you are supposed to use Euclid's Algorithm right? I know how to do Euclid's Algorithm I just don't understand how to use it to solve the problem I have shown above. Please explain as much as you can, big test coming up soon!

2. ## calculation details

The typical question is to describe all x's such that
x = 11 mod (39), and
x = 7 mod (22)

Since 22 and 39 are relatively prime, you can find the following 2 relations:
22*16 = 1 mod 39, and
39*13 = 1 mod 22.

Then you make the number:
n = 11*22*16 + 7*39*13 + k * 22 * 39, with k an arbitrary integer
Note that:
n = 11 mod 39, and
n = 7 mod 22
so this satisfies what you're looking for.

Now:
n = 7421 + k*22*39, or
n = 7421 mod (22*39), or
n = 557 mod 858.

3. Originally Posted by steph3824
Here is a simple example.

x 11 (mod 39)
x 7 (mod 22)

I would greatly appreciate it if someone could explain how to do this. I know first of all that 39a+22b=1. I believe you are supposed to use Euclid's Algorithm right? I know how to do Euclid's Algorithm I just don't understand how to use it to solve the problem I have shown above. Please explain as much as you can, big test coming up soon!
I just asked a similar question in the Discrete section, you might get some additional info from that post. But I will explain what I've learned so far. If someone else has corrections or additions, please correct or enhance what I've said.

First set up the following variables: multiply your modulos together to get m=(30)(22)=858; set a1=11, a2=7; divide m by each modulo to get M1=858/39=22 and M2=858/22=39; let m1=39 and m2=22

Now set up the main equation for the CRT
x=a1*M1*y1 + a2*M2*y2

All that's left to do is figure out y1 and y2 so set up the following congruences:

M1*y1 $\equiv$ 1 (mod 39) and
M2*y2 $\equiv$ 1 (mod 22) which gives

22*y1 $\equiv$ 1 (mod 39)
39*y2 $\equiv$ 1 (mod 22)

After solving these, I get y1 = 16 and y2 = -9

x = (11)(22)(16) + (7)(39)(-9) = 1415 $\equiv$ 557 (mod 858) so

x = 557 + 858k, where k is an integer

test 557 - (22)(25) = 7 and 557 - (39)(14) = 11

Hope this helps

4. These were both very helpful, thank you