Find all solutions, if any, to the system of congruences x ≡ 7 (mod 9), x ≡ 4 (mod 12), and x ≡ 16 (mod 21) 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?
 A: $\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.
A: 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.
