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