# Finding values for Chinese Remainder Theorem

So I have looked over a lot of the other Chinese Remainder Theorems on here and I still can not completely understand how to answer my question. The question is "Use the construction in the proof of Chinese remainder theorem to find all solutions to the system of congruences." \begin{align} x &\equiv 1 \pmod{3} \\ x &\equiv 0 \pmod{4} \\ x &\equiv 1 \pmod{5} \end{align} I found my $M=60$, $M_1= 20$, $M_2=15$, $M_3=12$, $a_1=1$, $a_2=0$, $a_3=1$, but I do not understand how to calculate $y_1$, $y_2$, and $y_3$. I think I am supposed to do something with the Euclidian algorithm but I am not sure.

$\ 3,5\mid x\!-\!1\!\iff\!15\mid x\!-\!1,\,$ So $\,{\rm mod}\ 15\!:\ x=4n\equiv 1\equiv 16\!\iff\!\color{#c00}{n\equiv 4},\,$ so $\,x = 4(\color{#c00}{4+15k})$

• Honestly I don't know why but I can't even wrap my brain about this theorem for some reason can you either show an example of another problem or explain the steps a little more please
– rick
Mar 14, 2014 at 4:10

Let $x = a_{i}$ (mod $M_{i}$), and we have a sequence of congruences. Let $M = \prod_{i=1}^{n} M_{i}$. Then $y_{i} = (\frac{M}{M_{i}})^{-1}$ (mod $M_{i}$).

So your $y_{1} = 20^{-1}$ (mod $3$).

You need to find y1,y2 and y3 such that M1*y1 ≡ 1(mod m1) and so on.

Now M1 = 20 and m1 = 3. So, we need y1 such that:

20 * y1 ≡ 1 (mod 3)

2 * y1 ≡ 1 (mod 3) (Reducing 20 modulo 3)

It is clear now that y1 should be 2.

But it will not be so clear if the numbers were a little bigger.

e.g., If we have to find inverse of 34 modulo 125 , a more general method is required.

Here's where the extended euclidean algorithm comes in.

Calculate the gcd of 34 and 125 using extended euclidean algorithm.

125 = 3 * 34 + 23 or 23 = 125 - 3 * 34

34 = 1 * 23 + 11 or 11 = 34 - 23 = 4 * 34 - 125 (using the value of 23 above)

23 = 2 * 11 + 1 or 1 = 23 - 2 * 11 = 3 * 125 - 11 * 34

-11 * 34 = 1 - 2 * 125

-11 * 34 ≡ 1 (mod 125)

The coefficient of 34(-11) is its inverse modulo 125.

A similar process can be applied to calculate y1,y2,y3.

Once you have those , the solution is:

x = Σ(ai*Mi*yi)

• Hi new user. Welcome! You might want to use MathJax in future :) Mar 14, 2014 at 19:18
• @Shaun Thanks for the advice. Mar 14, 2014 at 19:24
• @merlyn so would Y2=3 and Y3=2?
– rick
Mar 14, 2014 at 20:05
• @rick Y2=3 is correct but how did you get Y3=2? Mar 14, 2014 at 20:12
• @rick Y3=-2 or 3. Mar 14, 2014 at 20:29