Sum of Integer Ideals is Greatest Common Divisor

From ProofWiki

Jump to: navigation, search

Theorem

Let $\left({m}\right)$ and $\left({n}\right)$ be ideals of the integers $\Z$.

Let $\left({d}\right) = \left({m}\right) + \left({n}\right)$.

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

By Sum of Ideals is an Ideal we have that $\left({d}\right) = \left({m}\right) + \left({n}\right)$ is an ideal of $\Z$.

By Ring of Integers is Principal Ideal Domain we have that $\left({m}\right)$, $\left({n}\right)$ and $\left({d}\right)$ are all necessarily principal ideals.

$\left({m}\right) = m \Z, \left({n}\right) = n \Z$

Thus:

$\left({d}\right) = \left({m}\right) + \left({n}\right) = \left\{{x \in \Z: \exists a, b \in \Z: x = a m + b n}\right\}$

That is, $\left({d}\right)$ is the set of all integer combinations of $m$ and $n$.

The result follows by Bézout's Lemma.

$\blacksquare$