## Proof That We Can Write the Greatest Common Divisor iof Two Numbers as a Linear Combination of Those Numbers

Theorem
Given integers
$a, \; b$
with greatest common divisor
$d$
, there exist integers
$m, \; b$
such that
$d=ma+nb$
.
Proof
Consider the set
$\{ S: xa+yb \gt 0 \}$
where
$x, \; y$
are integers. Each
$xa+yb \in S$
is an integer and
$S$
is not empty because for example,
$a \in S$
. By the Well Ordering Principle there is a smallest element
$s$
of
$S$
.
The Division Algorithm tells us that on dividing
$a$
by
$s$
we get
$a=sq+r$
for some integers
$q, \; r, \; 0 \le r \lt s$
. But then
$r=a-sq=a-(ma+nb)=a(1-mq)+(-nq)b$
showing that
$r$
is a linear combination of
$a, \; b$
. If
$r \gt 0$
then
$r \in S$
and
$r \lt s$
so
$r=0$
and

and
$s | a$
. Similarly
$s | b$
and
$s=d$
the greatest common divisor of
$a, \; b$
.