[Math] Find all solutions, if any, to the system of congruences x ≡ 7 (mod 9), x ≡ 4 (mod 12), and x ≡ 16 (mod 21)

chinese remainder theoremdiscrete mathematics

Using the Chinese Remainder Theorem:

$$m=9\cdot21\cdot12=2268$$

$$M_1=\frac{2268}{9}=252, \space M_2=\frac{2268}{12}=189, \space M_3=\frac{2268}{21}=108$$

but when trying to find the inverse: $252(y_1) \equiv 1 \pmod 9$, $189(y_2) \equiv 1 \pmod{12}$, and $108(y_3) \equiv 1 \pmod{21}$ have no inverse. But the answer is given as $16+252k$. How is this so?

Best Answer

$\begin{eqnarray}&&x\equiv\ \ 7\equiv \color{#c00}{16}\pmod 9\\ &&x\equiv\ \ 4\equiv \color{#c00}{16}\pmod {12}\\ &&x\equiv 16\equiv \color{#c00}{16}\pmod{21}\end{eqnarray}$ $\iff$ $\,9,12,21\mid x\!-\!\color{#c00}{16}$ $\iff$ ${\rm lcm}(9,12,21)\mid x\!-\!\color{#c00}{16}$

Finally $\ {\rm lcm}(9,12,21) = {\rm lcm}(3^{\large\color{#0a0} 2},\,3\cdot 2^{\large \color{#0a0}2},\,3\cdot 7) = 3^{\large\color{#0a0}2}\cdot 2^{\large\color{#0a0}2}\cdot 7 = 252.$


Alternatively, algorithmically, by the third congruence $\ x = 16+21n\,$ for an integer $\,n.\,$ Hence

${\rm mod}\ 12\!:\ 4\equiv x= 16+21n\equiv 4-3n\iff 3n\equiv 0\iff 12\mid 3n\iff 4\mid n\iff\ n = 4k$

${\rm mod}\,\ \ 9\!:\,\ 7 \equiv x = 16+84k\equiv 7+3k\ \iff 3k\equiv 0\iff\,\ 9\mid3k\,\iff 3\mid k\,\iff\, k = 3j$

We've proved $\ x = 16+84(3j) = 16+252j.$

Remark $\ $ Note, in particular, that there is no need to split into pairwise coprime moduli as in David's answer. Generally, proceeding as above will yield a simpler method - often much so.