Congruence Mod mn: Only When gcd(m, n) = 1

A student sees two congruences,

a \equiv b \pmod{m} \qquad \text{and} \qquad a \equiv b \pmod{n},

and writes down, feeling very efficient,

a \equiv b \pmod{mn}.

It looks natural. Both m and n divide a - b, so surely mn divides a - b. Right? Not quite. This shortcut only works when \gcd(m, n) = 1. The moment m and n share a prime factor, the "combine moduli by multiplying" step stops being valid and starts producing wrong answers on exams.

The claim, precisely

The correct statement — a corollary of the Chinese Remainder Theorem — is:

Combining congruences

If a \equiv b \pmod{m} and a \equiv b \pmod{n}, then

a \equiv b \pmod{\operatorname{lcm}(m, n)}.

When \gcd(m, n) = 1, you get \operatorname{lcm}(m, n) = mn, and the shortcut works. When \gcd(m, n) > 1, you get \operatorname{lcm}(m, n) < mn, and the shortcut over-claims.

Why: m \mid (a - b) and n \mid (a - b) together say that (a - b) is a common multiple of m and n. The smallest common multiple it must be a multiple of is \operatorname{lcm}(m, n), not mn.

A concrete counterexample

Take a = 10, b = 4, m = 2, n = 6.

10 \equiv 4 \pmod{2}? \; 10 - 4 = 6, and 2 \mid 6. Yes.
10 \equiv 4 \pmod{6}? \; 6 \mid 6. Yes.

So both hypotheses hold. The bogus shortcut would give 10 \equiv 4 \pmod{12}. Check: 10 - 4 = 6, and 12 \nmid 6. False. The correct conclusion uses \operatorname{lcm}(2, 6) = 6: 10 \equiv 4 \pmod{6}, which is exactly what you already knew.

The reason the shortcut broke: \gcd(2, 6) = 2 \neq 1. The moduli 2 and 6 share the prime 2, so multiplying them double-counts that prime.

Why coprimality is exactly the right condition

Write a - b = d. You have m \mid d and n \mid d. Factor each modulus into primes and look at the prime p. If p appears \alpha times in m and \beta times in n, then p appears at least \max(\alpha, \beta) times in d. The smallest guaranteed power of p dividing d is p^{\max(\alpha, \beta)}, not p^{\alpha + \beta}.

\operatorname{lcm}(m, n) takes \max(\alpha, \beta) for every prime — exactly the right bookkeeping.
mn takes \alpha + \beta — too much, unless one of the two is always zero.

"One of the two is always zero" is exactly the condition \gcd(m, n) = 1: no prime appears in both.

For $m = 12$ and $n = 18$, both share the prime $3$. The lcm takes $\max$ of powers ($2^2$ from $m$, $3^2$ from $n$ — the higher power each time), giving $36$. The product $mn = 216$ double-counts the shared $3$ and the shared $2$, overshooting by a factor of $\gcd(m, n) = 6$.

The cleanest way to remember

There is a one-liner that encodes the whole rule:

mn \;=\; \gcd(m, n) \cdot \operatorname{lcm}(m, n).

So "mod mn" matches "mod \operatorname{lcm}" exactly when \gcd(m, n) = 1. That is the coprimality condition, stated in a single identity.

Where the shortcut *does* work

Take a = 23, b = 2, m = 3, n = 7. Check \gcd(3, 7) = 1. ✓

23 - 2 = 21 = 3 \times 7, so 3 \mid 21 and 7 \mid 21. Both hypotheses hold.
Since \gcd(3, 7) = 1, the shortcut is legal: 23 \equiv 2 \pmod{21}.

Check: 21 \mid 21. ✓

This is the Chinese Remainder Theorem doing its work. Two coprime moduli can be combined by multiplication — and the new modulus mn is equivalent to the pair (m, n) of original moduli, carrying exactly the same information about a - b.

Where this trap shows up on exams

Most commonly on questions like "find all x with x \equiv 1 \pmod{4} and x \equiv 1 \pmod{6}." The wrong answer is "x \equiv 1 \pmod{24}" (claiming 24 solutions per cycle of 24). The right answer uses \operatorname{lcm}(4, 6) = 12: x \equiv 1 \pmod{12}. You are claiming twice as many solutions as actually exist — a dangerous kind of mistake because the extra solutions will fail downstream checks.

Whenever you are about to combine two congruences into a single one by multiplying moduli, pause and ask: is the gcd of the two moduli really 1? If yes, proceed. If no, use the lcm, not the product.