# Thread: Getting stuck on the CRT

1. ## Getting stuck on the CRT

Ok, here's the problem.
x 2 (mod 5)
x 1 (mod 7)
x 3 (mod 11)

Here is what I have so far..

M=5x7x11=385

M1=385/5=77
m2=385/7=55
M3=385/11=35

x=(a1xM1xy1)+(a2xM2xy2)+(a3xM3xy3)

77y1 1 (mod 5)
55y2 1 (mod 7)
35y3 1 (mod 11)

The issue I am having is getting the correct numbers for y1,y2,y3. What I am doing is using the Extended Euclidean Algorithm, but I'm not getting the numbers that are shown in my book, so I'm thinking that using the Extended Euclidean Algorithm isn't the proper way to figure out what the y's are. SO for example..I know that the solution to 77y1 1 (mod 5) is 3(mod 5), I just don't know where the 3 is coming from.

I hope this has all made sense, I explained this as clearly as possible!! Thanks for the help!

2. ## make the numbers smaller

Everything looks right, but your numbers are too big. For instance,

77 = 2(5), so you're looking for y s.t. 2y=1(5). Clearly this is 3.

Similarly,

55 = 6 (7), so you're looking for 6y = 1 (7) and y = 6.

Can you keep going?

3. qmech, that made perfect sense. I understand it now, thanks!