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.