[Math] Solving simultaneous congruences

modular arithmetic

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?

Best Answer

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.

Related Question