Question

Solve the following simultaneous linear congruences.

a) x ? 1 (mod 3), x ? 2 (mod 4), x ? 3 (mod 5).
b) x ? 4 (mod 10), x ? 8 (mod 12), x ? 6 (mod 18).

Answer 1

a. The moduli are coprime, so you can apply the Chinese remainder theorem directly. Let

$x=4\cdot5+3\cdot5+3\cdot4$

• Taken mod 3, the last two terms vanish, and $20\equiv2\pmod3$ so we need to multiply by the inverse of 2 modulo 3 to end up with a remainder of 1. Since $2\cdot2\equiv4\equiv1\pmod3$, we multiply the first term by 2.

$x=4\cdot5\cdot2+3\cdot5+3\cdot4$

• Taken mod 4, the first and last terms vanish, and $15\equiv3\pmod4$. Multiply by the inverse of 3 modulo 4 (which is 3 because $3\cdot3\equiv9\equiv1\pmod4$), then by 2 to ensure the proper remainder is left.

$x=4\cdot5\cdot2+3\cdot5\cdot3\cdot2+3\cdot4$

• Taken mod 5, the first two terms vanish, and $12\equiv2\pmod5$. Multiply by the inverse of 2 modulo 5 (3, since $3\cdot2\equiv6\equiv1\pmod5$) and again by 3.

$x=4\cdot5\cdot2+3\cdot5\cdot3\cdot2+3\cdot4\cdot3\cdot3$

$\implies x=238$

By the CRT, we have

$x\equiv238\pmod{3\cdot4\cdot5}\implies x\equiv-2\pmod{60}\implies\boxed{x\equiv58\pmod{60}}$

i.e. any number $58+60n$ (where $n$ is an integer) satisifes the system.

b. The moduli are not coprime, so we need to check for possible contradictions. If $x\equiv a\pmod m$ and $x\equiv b\pmod n$, then we need to have $a\equiv b\pmod{\mathrm{gcd}(m,n)}$. This basically amounts to checking that if $x\equiv a\pmod m$, then we should also have $x\equiv a\pmod{\text{any divisor of }m}$.

$x\equiv4\pmod{10}\implies\begin{cases}x\equiv4\equiv0\pmod2\\x\equiv4\pmod5\end{cases}$

$x\equiv8\pmod{12}\implies\begin{cases}x\equiv0\pmod2\\x\equiv2\pmod3\end{cases}$

$x\equiv6\pmod{18}\implies\begin{cases}x\equiv0\pmod2\\x\equiv0\pmod3\end{cases}$

The last congruence conflicts with the previous one modulo 3, so there is no solution to this system.