Smallest Positive Integer Combination is Greatest Common Divisor
Theorem
Let $a, b \in \Z_{>0}$ be (strictly) positive integers.
Let $d \in \Z_{>0}$ be the smallest positive integer such that:
- $d = a s + b t$
where $s, t \in \Z$.
Then:
- $(1): \quad d \divides a \land d \divides b$
- $(2): \quad c \divides a \land c \divides b \implies c \divides d$
where $\divides$ denotes divisibility.
That is, $d$ is the greatest common divisor of $a$ and $b$.
Proof 1
Let $D$ be the subset of $\Z_{>0}$ defined as:
- $D = \set {a s + b t: s, t \in \Z, a s + b t > 0}$
Setting $s = 1$ and $t = 0$ it is clear that $a = \paren {a \times 1 + b \times 0} \in D$.
So $D \ne \O$.
By Set of Integers Bounded Below by Integer has Smallest Element, $D$ has a smallest element $d$, say.
Thus $d = a s + b t$ for some $s, t \in \Z$.
Proof of $(1)$
From the Division Theorem we can write $a = q d + r$ for some $q, r$ with $0 \le r < d$.
If $r \ne 0$ we have:
| \(\ds r\) | \(=\) | \(\ds a - q d\) | ||||||||||||
| \(\ds \) | \(=\) | \(\ds a - q \paren {a s + b t}\) | ||||||||||||
| \(\ds \) | \(=\) | \(\ds a \paren {1 - q s} + b \paren {-q t}\) |
So by definition of $D$, it is clear that $r \in D$.
But $r < d$ which contradicts the stipulation that $d$ is the smallest element of $D$.
Thus $r = 0$ and so $a = q d$.
That is $d \divides a$.
By the same argument, it follows that $d \divides b$ also.
$\Box$
Proof of $(2)$
Let $c \divides a$ and $c \divides b$.
Then:
- $\exists u, v \in \Z: a = c u, b = c v$
Thus:
| \(\ds d\) | \(=\) | \(\ds a s + b t\) | ||||||||||||
| \(\ds \) | \(=\) | \(\ds c u s + c v t\) | ||||||||||||
| \(\ds \) | \(=\) | \(\ds c \paren {u s + v t}\) |
demonstrating that $c \divides d$.
$\blacksquare$
Proof 2
From Bézout's Identity we have: Let $a, b \in \Z$ such that $a$ and $b$ are not both zero.
Let $\gcd \set {a, b}$ be the greatest common divisor of $a$ and $b$.
Then:
- $\exists x, y \in \Z: a x + b y = \gcd \set {a, b}$
Furthermore, $\gcd \set {a, b}$ is the smallest positive integer combination of $a$ and $b$.
In this instance, $a, b \in \Z_{>0}$ and are therefore both non-zero.
The result then follows by definition of greatest common divisor:
$d = \gcd \set {a, b}$ if and only if:
- $(1): \quad d \divides a \land d \divides b$
- $(2): \quad c \divides a \land c \divides b \implies c \divides d$
$\blacksquare$