Thursday, November 1, 2018

elementary number theory - Chinese Remainder Theorem clarification

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

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...