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

Question

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?

Answer 1

Hint. You have to split the congruences into forms with relatively prime moduli before you can use CRT. So you would have for a start $$\eqalign{ x&\equiv7\pmod9\cr x&\equiv4\pmod3\cr x&\equiv4\pmod4\cr x&\equiv16\pmod3\cr x&\equiv16\pmod7\ ,\cr}$$ which can be simplified to $$\eqalign{ x&\equiv7\pmod9\cr x&\equiv1\pmod3\cr x&\equiv1\pmod3\cr x&\equiv0\pmod4\cr x&\equiv2\pmod7\ .\cr}$$ Now the second and third are the same congruence so we don't need to write it twice: $$\eqalign{ x&\equiv7\pmod9\cr x&\equiv1\pmod3\cr x&\equiv0\pmod4\cr x&\equiv2\pmod7\ .\cr}$$ At this stage the first and second congruences involve moduli, one of which is a factor of the other. Therefore we have a potential contradiction here and we have to check to see whether there actually is a contradiction or not. In fact, $$\eqalign{ x\equiv7\pmod9\quad &\Rightarrow\quad x=7+9k\cr &\Rightarrow\quad x=1+3(2+3k)\cr &\Rightarrow\quad x\equiv1\pmod3\ ,\cr}$$ so the second congruence is redundant and we have to solve $$\eqalign{ x&\equiv7\pmod9\cr x&\equiv0\pmod4\cr x&\equiv2\pmod7\ .\cr}$$ This is now a "standard" CRT problem because $9,4,7$ are pairwise coprime, and I will leave it up to you. Note that the modulus in the answer will be $9\times4\times7=252$, not $9\times21\times12$ as you claimed.

Addendum. Bill Dubuque has given a very nice short cut in his answer. However you should still know the general method as there won't always be a short cut like this.

Answer 2

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