Smallest Positive Integer Combination is Greatest Common Divisor/Proof 2

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

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$