Chinese remainder theorem for noncoprime moduli ($a\equiv b(\mathrm{mod}\gcd (m,n))$)

For positive integer moduli $m,n$, the simultaneous integer congruences $x\equiv a(\mathrm{mod}m)$ and $x\equiv b(\mathrm{mod}n)$ are solvable exactly when $a\equiv b(\mathrm{mod}\gcd (m,n))$. When solvable, they determine a unique congruence class modulo $\mathrm{lcm}(m,n)$. To see the condition, put $x=a+mk$: the remaining equation is the linear congruence $mk\equiv b-a(\mathrm{mod}n)$, which is solvable exactly when the greatest common divisor divides $b-a$.

For example, $x\equiv 1(\mathrm{mod}6)$ and $x\equiv 3(\mathrm{mod}8)$ give $6k\equiv 2(\mathrm{mod}8)$, hence $3k\equiv 1(\mathrm{mod}4)$ and $k\equiv 3(\mathrm{mod}4)$. Thus $x\equiv 19(\mathrm{mod}24)$. Changing the second remainder to two makes the conditions incompatible: the first requires an odd integer, while the second requires an even integer. Article 32 of Carl Friedrich Gauss's Disquisitiones arithmeticae gives a successive construction for simultaneous remainders, including the greatest common divisor and least common multiple that enter this general case. ^[ref]