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\]
.