Resolving system with Chinese Remainder Theorem

Question

Consider following system : \begin{cases} x \equiv 2 \, \text{mod} \, 9 \\ x \equiv 3 \, \text{mod} \, 5 \\ x \equiv 8 \ \text{mod} \, 21 \end{cases} I can't apply the Chinese remainder theorem because the $\text{gcd}(21,9) \neq 1.$ So I want to factorize $21$ and $9$ in prime factors and make new equations. A theorem in my books says if the $\text{gcd}(n,m) = 1$ then $ x \equiv x' \, \text{mod}\ nm \iff \begin{cases} x \equiv x' \, \text{mod} \, n \\ x \equiv x' \, \text{mod} \, m \\ \end{cases} $. But how do I apply this with the first equation. Because $9=3*3$ and the $\text{gcd}(3,3) \neq 1$. I heard some solution who said that $x \equiv 2\,\text{mod}\, 9$ is the same as $x \equiv 2\,\text{mod}\, 3$ but I don't understand why they are the same. Thanks in advance!

Answer 1

Hint. Since $21=3\cdot 7$, by CRT, the system is equivalent to $$\begin{cases} x \equiv 2 \, \text{mod} \, 9 \\ x \equiv 3 \, \text{mod} \, 5 \\ x \equiv 8 \ \text{mod} \, 3\\ x \equiv 8 \ \text{mod} \, 7 \end{cases}$$ That is $$\begin{cases} x \equiv 2 \, \text{mod} \, 9 \\ x \equiv 3 \, \text{mod} \, 5 \\ x \equiv 2 \ \text{mod} \, 3\\ x \equiv 1 \ \text{mod} \, 7 \end{cases}$$ Since $x \equiv 2\ \text{mod} \, 9$ implies $x \equiv 2\ \text{mod} \, 3$,it remains to solve $$\begin{cases} x \equiv 2 \, \text{mod} \, 9 \\ x \equiv 3 \, \text{mod} \, 5 \\ x \equiv 1 \ \text{mod} \, 7 \end{cases}$$ Now apply CRT.