So I have been trying to understand the Chinese Remainder Theorem for some time now and I just don't know what is going on. I have looked at the definition many times and I understand congruence equations just about. I have an exam on this in a few days so I really want to understand it! Here is a question from a past exam. I have the solution, but just dont understand what is going on so an explanation would be amazing! Thanks.
Here is the question:
Use the Chinese Remainder Theorem to find the smallest value of $x$ for which
$$\begin{align} x&=3\mod 5, \\ x&=2 \mod 3, \\x&=4 \mod 7.\end{align}$$
Solution
For $N=5 \times 7 \times 3 = 105$, solve the equations for $y_1,y_2,y_3$:
$$\frac{105}{5}y_1=1 \mod 5 \implies 21y_1=1 \mod 5 \implies y_1=1,3 \mod 5$$
So I understand everything up until here!
$$\frac{105}{3}y_2=1 \mod 3 \implies
2y_2=1 \mod 3 \implies
y_2=2 \mod 3$$
and
$$\frac{105}{7}y_3=1 \mod 7 \implies 15y_3=1 \mod7 \implies y_3=1, 3 \mod7$$
How did he get $y_1=1,3$ without doing any working out? And I get that $5$ doesnt divide $21 \times 3 - 1$ so how is $y_1=3$ a solution?
Anyway, the rest of the solution:
$$\begin{align}x&=3 \times 21 \times 1 + 2 \times 35 \times 2 + 4\times15+1 \mod 105 \\
&=63 +140 +60 \mod 105 \\
&=263 \mod 105 \\
&=53 \mod 105\end{align}$$
So I pretty much don't know what is going on from where I have highlighted. Could someone please explain how to solve for each $y$, and explain where the $4$ came from in the calculation for $x$?
Please only use the method I have shown as I must do it the same way or lose marks. Many thanks.
No comments:
Post a Comment