GCD from Generator of Ideal

Theorem

Let $m, n \in \Z$, with either $m \ne 0$ or $n \ne 0$.

Let $I = \ideal {m, n}$ be the ideal generated by $m$ and $n$.

Let $d$ be a non-negative generator for the principal ideal $I$.

Then:

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

where $\gcd \set {m, n}$ denotes the greatest common divisor of $m$ and $n$.

First we show that such an element $d$ exists.

If $e < 0$, then since the units of $\Z$ are $\set {\pm 1}$, we have by definition that $-e$ is an associate of $e$.

Therefore by $(3)$ of Principal Ideals in Integral Domain $-e > 0$ is also a generator of $I$.

In particular setting $d = \max \set {e, -e}$, $d$ is a non-negative generator of $I$.

By Bézout's Identity, we are required to show that $d$ is the smallest positive integer combination of $m$ and $n$.

By definition:

$I = \set {a m + b n: a, b \in \Z}$

Thus we are required to show that $d$ is the smallest positive element of $I$.

Suppose that $d' \le d$ is a positive element of $I$, not larger than $d$.

By hypothesis $d$ generates $I$, so there exists $a \in \Z$ such that $d' = ad$.

Since $d > 0$, we can therefore write $a = \dfrac {d'} d \in \Q$.

Moreover, because $d' > 0$, by $(6)$ of Properties of Ordered Ring we have:

$0 = \dfrac 0 d < \dfrac {d'} d$

Using the hypothesis that $d' \le d$, we have the pair of inequalities:

$0 < a = \dfrac {d'} d \le 1$

By the definition we have $a \in \Z$, so this shows that $\dfrac {d'} d = 1$.

It follows that $d' = d$.

Therefore there is no positive element of $I$ smaller than $d$.

$\blacksquare$