Intersection of Congruence Classes Modulo m

Theorem

Let $\mathcal R_m$ denote congruence modulo $m$ on the set of integers $\Z$.

Then $\mathcal R_m \cap \mathcal R_n = \mathcal R_{\operatorname{lcm} \left\{{m, n}\right\}}$, where $\operatorname{lcm} \left\{{m, n}\right\}$ is the lowest common multiple of $m$ and $n$.

In the language of modulo arithmetic, this is equivalent to:

$a \equiv b \pmod m, a \equiv b \pmod n \implies a \equiv b \pmod {\operatorname{lcm} \left\{{m, n}\right\}}$

Corollary

If $m \perp n$ then $\mathcal R_m \cap \mathcal R_n = \mathcal R_{m n}$.

Proof

Let $\left({a, b}\right) \in \mathcal R_m \cap \mathcal R_n$.

That is, let $\left({a, b}\right) \in \mathcal R_m$ and $\left({a, b}\right) \in \mathcal R_n$.

That means, by definition of congruence:

• $a \equiv b \pmod m$
• $a \equiv b \pmod n$

Thus by definition of congruence:

$\exists r, s \in \Z: a - b = rm, a - b = sn$

Let $d = \gcd \left\{{m, n}\right\}$ so that $m = d m', n = d n', m' \perp n'$.

Substituting for $m$ and $n$:

$r d m' = s d n'$ and so $r m' = s n'$.

So $n' \backslash r m'$ and $m' \perp n'$ so by Euclid's Lemma $n' \backslash r$.

So we can put $r = k n'$ and get:

$a - b = r m = k m n' = k m \dfrac n d = k \dfrac {m n} d$

But:

$\dfrac {m n} d = \dfrac {m n} {\gcd \left\{{m, n}\right\}}$

So by Product of GCD and LCM $a - b = k \operatorname{lcm} \left\{{m, n}\right\}$

So $a \equiv b \pmod {\operatorname{lcm} \left\{{m, n}\right\}}$ and hence the result.

$\blacksquare$

Proof of Corollary

$m \perp n$ means $\gcd \left\{{m, n}\right\} = 1$.

From Product of GCD and LCM it follows that $\operatorname{lcm} \left\{{m, n}\right\} = m n$.

Hence the result, from above.

$\blacksquare$

Sources

• Allan Clark: Elements of Abstract Algebra (1971)... (previous)... (next): $\S 18 \beta$
• Allan Clark: Elements of Abstract Algebra (1971)... (previous)... (next): $\S 23 \delta$