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

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

.