Smallest Positive Integer Combination is Greatest Common Divisor/Proof 1

From ProofWiki
Jump to navigation Jump to search


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$.


$(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$.


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.


Proof of $(2)$

Let $c \divides a$ and $c \divides b$.


$\exists u, v \in \Z: a = c u, b = c v$


\(\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$.