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

• Did you made a typo somewhere? I can't see where the $+1$ come from, and at any rate, it does not sum up to $263$. Also, the $4$ is the remainder as stated in the question. I also can't see how $y_{3}$ and $y_{1}$ could take the value of $3$ either. – Gina Jan 4 '14 at 2:03
• oh yeah i see the 4 now, noticed that at last minute... i dont know i am just copying the solutions and it does say +1... – Bernard.Mathews Jan 4 '14 at 2:04

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.

• so do you mean $y_1$ does not equal 3? – Bernard.Mathews Jan 4 '14 at 2:00
• Yes, $y_1=3$ can't happen. – Ragnar Jan 4 '14 at 2:03
• and it is meant to read $y_1=1 \mod 5$ and $y_1=3 \mod 5$ instead of $y_1=1, 3$ – Bernard.Mathews Jan 4 '14 at 2:03
• are you sure? I mean, i get the same answer as you but could his solutions really be wrong? ahhhhhh!! this is exactly why i am confused otherwise it makes sense – Bernard.Mathews Jan 4 '14 at 2:04
• do you have a link to the solution maybe? – Ragnar Jan 4 '14 at 2:05

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}

• Great idea, will look at this too! Thanks!!!! – Bernard.Mathews Jan 4 '14 at 2:43
• If you write those middle nine equations in vector form then everything becomes clearer - see my answer. – Bill Dubuque Jan 4 '14 at 3:15
• They are arranged as column vectors rather than row vectors. That was the idea of my edit. – robjohn Jan 4 '14 at 4:25
• This question is now over $4$ years old but how did you arrive at $21, 70,$ and $15$ (the red-colored numbers)? – Remy Mar 22 '18 at 19:42
1. First we look for $y_1=\displaystyle\frac1{3\cdot 7}$ among numbers modulo $5$, $\$ $y_2=\displaystyle\frac1{5\cdot 7}$ among numbers modulo $3$ and $y_3=\displaystyle\frac1{3\cdot 5}$ among numbers modulo $7$.
2. With these, $x\equiv 3\cdot 21\cdot y_1+2\cdot 35\cdot y_2+4\cdot 15\cdot y_3$ will have $$x\equiv 3\cdot 21\cdot y_1\equiv 3\cdot 1=3\pmod5$$ and similarly for the other two.

The "$,3$" makes no sense for me. E.g., modulo $7$, we know that $15\equiv 1\pmod7$, so that $15y_3\equiv 1\pmod7$ is equivalent to $y_3\equiv1\pmod7$, because congruent numbers may be replaced by each other in congruences (or, simply because $14y_3\equiv 0\pmod7$). The same happens with $21y_1\equiv 1\pmod5$, it straightly implies that $y_1\equiv 1\pmod5$.

• thanks. so is $y_1=3 \mod 5$ correct then? – Bernard.Mathews Jan 4 '14 at 2:13
• No. If $21y_1\equiv 1\pmod5$ then $y_1=(21y_1-20y_1)\equiv 1\pmod5$. – Berci Jan 4 '14 at 2:17
• aaaaaah okay thanks. I get the same answer as you and person above for y1 but why are the solutions saying 3! thanks – Bernard.Mathews Jan 4 '14 at 2:18

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