= Chinese remainder theorem for noncoprime moduli
{c}
{title2=$a\equiv b\pmod{\gcd(m,n)}$}
For positive <integer moduli> $m,n$, the simultaneous <integer congruences> $x\equiv a\pmod m$ and $x\equiv b\pmod n$ are solvable exactly when $a\equiv b\pmod{\gcd(m,n)}$. When solvable, they determine a unique <congruence class> modulo $\operatorname{lcm}(m,n)$. To see the condition, put $x=a+mk$: the remaining equation is the <linear congruence> $mk\equiv b-a\pmod n$, which is solvable exactly when the <greatest common divisor> divides $b-a$.
For example, $x\equiv1\pmod6$ and $x\equiv3\pmod8$ give $6k\equiv2\pmod8$, hence $3k\equiv1\pmod4$ and $k\equiv3\pmod4$. Thus \b[$x\equiv19\pmod{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 \i[Disquisitiones arithmeticae] gives a successive construction for simultaneous remainders, including the <greatest common divisor> and <least common multiple> that enter this general case. https://la.wikisource.org/wiki/Disquisitiones_arithmeticae/Sectio_secunda[Gauss, Disquisitiones arithmeticae, section II, article 32; text from the 1870 collected edition]{ref}
Back to article page
