Intersection of Congruence Classes/Corollary

From ProofWiki
Jump to navigation Jump to search

Corollary to Intersection of Congruence Classes

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


If $m \perp n$ then $\RR_m \cap \RR_n = \RR_{m n}$.


Proof

By Intersection of Congruence Classes:

$\RR_m \cap \RR_n = \RR_{\lcm \set {m, n} }$

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

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

Hence the result.

$\blacksquare$