How can I apply the Chinese Remainder Theorem when a modulus is the square of another one?

Question

For example:

$$\begin{cases} x = 23 \mod 3 \\ x = 8 \mod 9 \\ x = 33 \mod 4 \end{cases}$$

I know that when two moduli are not mutually prime (for example: $$\begin{cases} x = n \mod 45 \\ x = m \mod 36 \end{cases}$$ ), one simply has to separate them in their divisors:$$\begin{cases} x = n \mod 9 \\ x = n \mod 5 \\ x = m \mod 9 \\ x = m \mod 4 \end{cases}$$ Where $n\mod{9} \text{ has to be equal to } m\mod{9}$. It doesn't work with squares though?

Answer 1

When one is a multiple of the other (which is a large case than your specific problem) you check they aren't contradictory then disregard the smaller one.

Anything which satisfies the multiple will have to also satisfy the smaller one.

So you problem is equivalent to:

$$\begin{cases} x = 8 \mod 9 \\ x = 33 \mod 4 \end{cases}$$

Answer 2

In general, a system of two congruences $$\begin{cases} x \equiv a \pmod m \\ x \equiv b \pmod n \\ \end{cases}$$ will have a solution if and only if $$ \gcd(m, n) \mid a - b. $$ In the particular case when $m \mid n$, the condition becomes $$ m \mid a - b, $$ that is $$ a \equiv b \pmod{m}. $$