Why do the moduli need to be relatively prime in order to apply the Chinese Remainder Theorem?

Question

Could someone provide a brief explanation or proof of why the moduli need to be relatively prime/coprime in order to apply the Chinese remainder theorem?

Answer 1

If you are asking, why the usual algorithm that arises from the proof of CRT fails to compute a solution, then check that the algorithm requires a representation $rm_1+sm_2=1$, where $m_1,m_2$ are the moduli and $r,s$ some integers. But Bezout's lemma tells, that this is only possible, if $m_1$ and $m_2$ are coprime.

If you are asking, why the CRT can not be extended to non-coprime moduli, then the answer is simply: Because it is wrong. There are systems of simultaneous congruences with non-coprime moduli, that have no solutions, so there can not be some theorem or procedure, which finds one.

Given any $m_1,m_2\in\mathbb Z$, such that $d=(m_1,m_2)>1$, consider the system: $$\begin{align*} x\equiv 0 \mod m_1 \\ x\equiv 1 \mod m_2 \end{align*}$$ Assume $x$ is a solution. It follows, that $d\mid m_1\mid x$ and $d\mid m_2\mid x-1$, so particularly $d\mid 1$, contradicting $d>1$.