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.

Both occurrences of $\ y_i = 1,3$ are misprints for $\ y_i \equiv 1.\,$ The rest of the solution looks fine. It is using the standard Chinese Remainder Theorem [CRT] formula, easily remembered as follows:

$\quad \begin{eqnarray} x\, =\, &a&\!\color{#0a0}{\overbrace{(3\cdot 7\ y_1)}^{\large \equiv\, 1\ ({\rm mod}\ 5)}} \,+\, &b& \overbrace{(\color{#c00}5\cdot 7\ y_2)}^{\large \equiv\, 1\ ({\rm mod}\ 3)}\, +\, &c&\overbrace{(3\cdot\color{#c00} 5\ y_3)}^{\large \equiv\, 1\ ({\rm mod}\ 7)}\quad {\bf [CRT]}\\ \\ \Rightarrow\ \ x\,\equiv\, &a&\ ({\rm mod}\ 5),\ \ x\equiv &b&\ ({\rm mod}\ 3),\ \ x\equiv &c&\ ({\rm mod}\ 7)\\ \end{eqnarray}$

because, $ $ e.g., $\ $ mod $\ 5,\,$ the 2nd and 3rd summands are $\equiv 0,\,$ both having factors of $\,\color{#c00}5.\,$

Hence $\ x\,\equiv\, a\,\color{#0a0}{(3\cdot 7\ y_1)}\equiv a\color{#0a0}{(1)} \equiv a\,\ ({\rm mod}\ 5),\ $ as desired. $ $ Similarly $ $ mod $\,3\,$ and $\,7.$

The key idea is that the braced terms are $\equiv 1$ mod one modulus, and $\equiv 0 $ mod all others. More clearly, if we write the system in vector form $\ x\equiv (a,b,c)\,$ mod $\,(5,3,7)$ then $\rm\,(CRT)$ is

$\quad x\, :=\, a\,\color{#0a0}{(1,0,0)} + b\,(0,1,0) + c\,(0,0,1)\equiv (a.b,c)\ $ as desired. $\qquad [\bf Linearity]$

by the green term $\,\color{#0a0}{g \equiv 1}\ ({\rm mod}\ 5),\ \color{#0a0}{g\equiv 0}\ ({\rm mod}\ 3),\ \color{#0a0}{g\equiv 0}\ ({\rm mod}\ 7),\ $ i.e. $\ \color{#0a0}{g\equiv (1,0,0)}\ {\rm mod}\ (5,3,7),\ $ and similarly for $\,(0,1,0)\,$ and $\,(0,0,1).$

Thus once we compute the solutions for the "basis" vectors $(1,0,0),\ (0,1,0),\ (0,0,1)$ we can exploit [Linearity] to generate the general solution as a linear combination of these solutions.

The innate algebraic structure will be clarified if you later study abstract algebra, where you will learn the ring theoretic view of CRT, and vector spaces and modules.

From $21y_1\equiv 1\mod 5$, it follows that $y\equiv 1\mod 5$, because $21\equiv 1\mod 5$. $y_1\equiv 3\mod 5$ is not possible.
Then, you get $y_2\equiv 2\mod 3$ and $y_3\equiv 1\mod 7$ (again, $3$ is not possible).

The last line (formula to calculate $x\mod 105$) is just a general formula.

Ok, I will answer this in a more abstract manner.

You know Cartesian coordinate right? Let's say you are in 3D space. You have 3 vector $i=(1,0,0);j=(0,1,0);k=(0,0,1)$. So how would you obtain a vector $(3,2,4)$? Simply make it $3i+2j+4k$.

Now think about it this way. $i,j,k$ corresponse to the 3 axis $x,y,z$ you have in 3D space. Once you have the 3 axis, it make it very easy for you to obtain a vector by just vector summation and scalar multiplication. It's in fact a basis for 3D space.

Back to this question, what you really care about is finding that "basis". That is, you want a number $i$ where $i\equiv 1(mod 3);i\equiv 0(mod 5);i\equiv 0(mod 7)$. Same for $j,k$ but they each corresponse to $5$ and $7$ respectively. Once you got $i,j,k$ you can solve for any $x$ given any modulo of $3,5,7$ by simply doing summation and multiplication. That is in fact the last step in the solution.

The previous step are just trying to find $i,j,k$. $i\equiv 0(mod 5);i\equiv 0(mod 7)$ which means $lcm(5,7)$ divide $i$. Now in a Chinese Remainder problem, the number are coprime, in other word, the only way this could happen is the lcm is the same as the product. Hence $lcm(5,7)=5\times 7=(3\times 5\times 7)/3$. In other word, the $\frac{105}{3}$ is exactly what is being done here. Once you got that $35$ divide $i$, you write $i=35y_{2}$. Since you need $i\equiv 1(mod 3)$ you have to find $y_{2}$ such that $35 y_{2}\equiv 1(mod 3)$. In general, this require the "extended Euclid algorithm", but judging from the solution, seems like you just need to make a guess.

I hope this help

I approach these problems as a set of three equations: $$ 5a_1+\color{#C00000}{21b_1}=1\implies21b_1=\color{#C00000}{21}\tag{1} $$ $$ 3a_2+\color{#C00000}{35b_2}=1\implies35b_2=\color{#C00000}{70}\tag{2} $$ $$ 7a_3+\color{#C00000}{15b_3}=1\implies15b_3=\color{#C00000}{15}\tag{3} $$ Note that the sum of $$ \left. \begin{align} 21&\equiv1\pmod{5}\\ 21&\equiv0\pmod{3}\\ 21&\equiv0\pmod{7} \end{align} \right\}\times3 $$ $$ \left. \begin{align} 70&\equiv0\pmod{5}\\ 70&\equiv1\pmod{3}\\ 70&\equiv0\pmod{7} \end{align} \right\}\times2 $$ $$ \left. \begin{align} 15&\equiv0\pmod{5}\\ 15&\equiv0\pmod{3}\\ 15&\equiv1\pmod{7} \end{align} \right\}\times4 $$ is a solution $$ \begin{align} 263&\equiv3\pmod{5}\\ 263&\equiv2\pmod{3}\\ 263&\equiv4\pmod{7} \end{align} \hphantom{\}\times1} $$

I solved the equations two at a time. Solving the first and second, you get $x = 8(\mod 15)$. Solving the first and third, you get $x = 18(\mod 35)$. Solving these two results simultaneously, you get $x = 53(\mod 105)$ which gives you all possible solutions for $x$.