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

Add comment

Security code
Refresh