Sum of Integer Ideals is Greatest Common Divisor

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\ideal m$ and $\ideal n$ be ideals of the integers $\Z$.

Let $\ideal d = \ideal m + \ideal n$.


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


Proof

By Sum of Ideals is Ideal we have that $\ideal d = \ideal m + \ideal n$ is an ideal of $\Z$.

By Ring of Integers is Principal Ideal Domain we have that $\ideal m$, $\ideal n$ and $\ideal d$ are all necessarily principal ideals.

By Subrings of Integers are Sets of Integer Multiples we have that:

$\ideal m = m \Z, \ideal n = n \Z$

Thus:

$\ideal d = \ideal m + \ideal n = \set {x \in \Z: \exists a, b \in \Z: x = a m + b n}$

That is, $\ideal d$ is the set of all integer combinations of $m$ and $n$.

The result follows by Bézout's Lemma.

$\blacksquare$


Sources