Finding values for Chinese Remainder Theorem

Question

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.

Answer 1

$\ 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})$

Answer 2

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$).

Answer 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)