Solving simultaneous congruences

The $3,2,1$ are from the right hand side of your congruences.

We know that $x=3$ is a solution to the first congruence, but this doesn't work as a solution to the next 2 congruences. So Chinese remaindering tells you to compute $(3\cdot 5)^{-1}=15^{-1}$ mod $7$. You find that this is $1$ (since $15(1)+(-2)7=1$). Thus $x=3\cdot 15\cdot 1$ ($=3 \cdot 15 \cdot 15^{-1} = 3 \cdot 1 =3$ (mod $7$) is still a solution of $x \equiv 3 \;\mathrm{mod}\; 7$ since $15\cdot 1 \equiv 1 \;\mathrm{mod}\;7$. What is special about this solution? Well, $x=3\cdot 15\cdot 1$ is also congruent to 0 modulo $3$ and $5$ (that's why we were messing with $(3\cdot 5)^{-1}=15^{-1}$).

Next, $x=2$ solves $x\equiv 2\;\mathrm{mod}\;5$, but again does not solve the other two congruences. So you compute $(3\cdot 7)^{-1}=21^{-1}$ mod $5$. You find that this is $1$ (since $21(1)+5(-4)=1$). Thus $x=2\cdot 21\cdot 1$ is still a solution of $x \equiv 2\;\mathrm{mod}\; 5$ while it is also congruent to 0 modulo $3$ and $7$. So now we've found a solution to the second congruence which doesn't interfere with the first and last congruences.

Finally, $x=1$ solves the third congruence but not the first two. So you compute $(5 \cdot 7)^{-1}=35^{-1}$ mod $3$. You find that this is $-1$ (since $35(-1)+3(12)=1$). Thus $x=1\cdot 35 \cdot (-1)$ is still a solution of $x\equiv 1\;\mathrm{mod}\;3$ while it is congruent to $0$ modulo $5$ and $7$.

So now each congruence has a solution which doesn't interfere with the other congruences. Thus adding the solutions together will solve all 3 at the same time.

Therefore, $x = 3\cdot 15\cdot 1 + 2\cdot 21\cdot 1 + 1\cdot 35 \cdot (-1) = 45+42-35=52$ is a solution to all 3 congruences. Since $105$ ($=3\cdot 5 \cdot 7$) is $0$ modulo $3$, $5$, and $7$, adding multiples of $105$ will still leave us with a solution to all $3$ congruences.


Although Bill Cook's answer is completely, 100% correct (and based on the proof of the Chinese Remainder Theorem), one can also work with the congruences successively; we know from the CRT that a solution exists.

Starting from $x\equiv 3\pmod{7}$, this means that $x$ is of the form $x=7k+3$ for some integer $k$. Substituting into the second congruence, we get $$7k+3 \equiv 2\pmod{5}.$$ Since $7\equiv 2\pmod{5}$, and $3\equiv -2\pmod{5}$, this is equivalent to $2k-2\equiv 2\pmod{5}$. Dividing through by $2$ (which we can do since $\gcd(2,5)=1$) we get $k-1\equiv 1\pmod{5}$, or $k\equiv 2\pmod{5}$. That is, $k$ is of the form $k=5r+2$ for some integer $r$.

Plugging this into $x=7k+3$ we have $x=7(5r+2)+3 = 35r + 17$.

Then plugging this into the third (and last) congruence, we get $$35r + 17\equiv 1\pmod{3}.$$ Now, $35\equiv -1\pmod{3}$, $17\equiv -1\pmod{3}$, so this is the same as $-r-1\equiv 1\pmod{3}$, or $r\equiv -2\equiv 1\pmod{3}$. That is, $r$ is of the form $3t+1$. Plugging that into $x$ we get $$x = 35r+17 = 35(3t+1)+17 = 105t + 52,$$ so that means that $x$ is of the form $x=52+105t$ for some integer $t$; that is, $x\equiv 52\pmod{105}$ is the unique solution modulo $3\times5\times 7$.


$ 2x \equiv -1\,$ mod $\,3,5,7\ \begin{array}{r}\iff 3,5,7\mid 2x\!+\!1\!\\ \iff\ \ \ 105\mid 2x\!+\!1\end{array}\!\iff\!$ mod $\,105\!:\ 2x \equiv -1\equiv 104\!\iff\! x\equiv 52\ $


HINT $\rm\quad y\: :=\: x-2 \equiv 0\pmod 5\ $ so $\rm\: y = 5\:j\:.\ $ Therefore

$\rm\ mod\ 3\!:\ {-}1\equiv y = 5\:j \equiv -j\ \Rightarrow\ j\equiv 1\ \Rightarrow\ y = 5\:(1+3\:k) = 5 + 15\:k$

$\rm\ mod\ 7\!:\ \ \ \ 1 \equiv y = 5 + 15\:k\equiv -2 + k\ \Rightarrow\ k\equiv 3\ \Rightarrow\ y = 5+15\:(3+7\:n) = 50 + 105\:n$

NOTE $\ $ Such exploitation of the "law of small numbers" often yields quicker soltuions than rote application of algorithms (Chinese Remainder Theorem, extended Euclidean algorithm, Hermite-Smith normal forms, etc).