Join of Sets of Integer Multiples is Set of Integer Multiples of GCD

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $m, n \in \Z$.

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

Let $r \in \Z$ such that:

$m \Z \subseteq r \Z$

and:

$n \Z \subseteq r \Z$


Then:

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

where $\gcd$ denotes greatest common divisor.


Proof

From Set of Integer Multiples is Integral Ideal, each of $m \Z$, $n \Z$, $r \Z$ and $\gcd \set {m, n} \Z$ are integral ideals.


Let $c \in \gcd \set {m, n} \Z$.

By definition of integral ideal:

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

By Set of Integer Combinations equals Set of Multiples of GCD:

$\exists x, y \in \Z: c = x m + y n$

But as $m \Z \subseteq r \Z$ and $n \Z \subseteq r \Z$:

$m \in r \Z$ and $n \in \r Z$

Thus by definition of integral ideal:

$x m + y n \in r \Z$


So:

$c \in \gcd \set {m, n} \Z \implies c \in r \Z$

and the result follows by definition of subset.

$\blacksquare$


Sources