Set of Integer Multiples of GCD

Theorem

Let $m, n \in \Z$.

Let $m \Z$ denote the set of integer multiples of $m$

Then:

$m \Z \cup n \Z \subseteq \gcd \set {m, n} \Z$

where $\gcd$ denotes greatest common divisor.

Proof

Let $x \in m \Z \cup n \Z$.

Then either:

$m \divides x$

or:

$n \divides x$

In both cases:

$\gcd \set {m, n} \divides x$

and so:

$x \in \gcd \set {m, n} \Z$

Hence by definition of subset:

$m \Z \cup n \Z \subseteq \gcd \set {m, n} \Z$

$\blacksquare$

Sources

• 1971: George E. Andrews: Number Theory ... (previous) ... (next): $\text {2-2}$ Divisibility: Exercise $11$