Solving simultaneous congruences

Question

Trying to figure out how to solve linear congruence by following through the sample solution to the following problem:

$x \equiv 3$ (mod $7$)
$x \equiv 2$ (mod $5$)
$x \equiv 1$ (mod $3$)

Let:
$n_1$ = 7
$n_2 = 5$
$n_3 = 3$

$N = n_1 \cdot n_2 \cdot n_3 = 105$

$m_1 = \frac{N}{n_1} = 15$

$m_2 = \frac{N}{n_2} = 21$

$m_3 = \frac{N}{n_3} = 35$

$gcd(m_1,n_1)$ = $gcd(15,7) = 1 = 15 \times 1 - 7 \times 2$ so $y_1 = 1$ and $x_1 = 15$
$gcd(m_2,n_2)$ = $gcd(21,5) = 1 = 21 \times 1 - 5 \times 4$ so $y_2 = 1$ and $x_2 = 21$
$gcd(m_3,n_3)$ = $gcd(35,3) = 1 = -35 \times 1 + 3 \times 12$ so $y_3 = -1$ and $x_3 = -35$

I understand up to this point, but the next line I don't get:

So $x = 15 \times 3 + 21 \times 2 - 35 \times 1 \equiv 52$ (mod $105$)

Where is the $\times 3$, $\times 2$, $\times 1$ from? Is it just because there are 3 terms, so it starts from 3 then 2 then 1? And where is the 52 coming from?

Answer 1

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

Answer 2

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.

Answer 3

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