Chinese remainder theorem for non-coprime moduli

Statement

Let $m$ and $n$ be positive integers, and let $a$ and $b$ be integers. Let $g = \gcd(m, n)$ and $M = \operatorname{lcm}(m, n)$. The system $x \equiv a \pmod m$, $x \equiv b \pmod n$ has an integer solution if and only if $a \equiv b \pmod g$. In this case, two solutions are congruent modulo $M$.

Remarks

When $g = 1$, this is the Chinese remainder theorem for two moduli. The condition is necessary: a solution $x$ gives $a \equiv x \equiv b \pmod g$, since $g$ divides $m$ and $n$. For $k$ moduli $n_1, \dots, n_k$, the system $x \equiv a_i \pmod{n_i}$ has a solution if and only if $\gcd(n_i, n_j) \mid a_i - a_j$ for all $i \neq j$. For example, $x \equiv 1 \pmod 4$ and $x \equiv 3 \pmod 6$ has the solutions $x \equiv 9 \pmod{12}$. But $x \equiv 1 \pmod 4$ and $x \equiv 2 \pmod 6$ has no solution.

Explanations

L1 human

When the moduli share a factor $g$, the two conditions both say something about $x$ modulo $g$. They must agree there. If they agree, there is a solution, and it is unique modulo the lcm.