Theorem: Let \(a\) and \(b\) be integers with \(b\not=0\). Then the greatest common divisor of \(a\) and \(b\) is the smallest positive value \(ax+by\) as \(x\) and \(y\) run through all integers.
Proof: Let \(d\) be the smallest positive value of \(ax+by\). Such a value exists by the Well Ordering Principle. We show that \(d=\mathrm{gcd}(a,b)\).
First, suppose that \(s\) is a common divisor of \(a\) and \(b\). Then \(s|(ax+by)\) by Proposition 2.1(ii), so \(s|d\). Therefore \(d\ge s\) by Proposition 2.1(iv). So \(d\) is greater than or equal to every common divisor of \(a\) and \(b\).
Second we show that \(d|a\). Apply the division algorithm to write \(a=qd+r\) with \(0\le r<d\). Multiply the equation \(ax+by=d\) by \(q\) to obtain \[ qax+qby=qd=a-r \] so \[ r=a(1-qx)+b(-qy). \] Since \(r\) is of the form \(ax'+by'\) for integers \(x'\) and \(y'\), and \(r<d\), we know that \(r\) cannot be positive. Therefore \(r=0\), so \(d|a\).
A similar argument shows that \(d|b\).
Since \(d\) is a common divisor of \(a\) and \(b\), and is greater than or equal to any other common divisor, we conclude that \(d=\mathrm{gcd}(a,b)\).
Theorem: \(\mathrm{lcm}(a,b)\mathrm{gcd}(a,b)=ab\).
Proof: First, notice that \(\mathrm{gcd}(a,b)\) divides \(ab\) because in fact it divides each of \(a\) and \(b\). Let \(T\) be any common multiple of \(a\) and \(b\), that is, any integer such that \(a|T\) and \(b|T\). Find \(x\) and \(y\) so that \[ ax+by=\mathrm{gcd}(a,b) \] and multiply this equation by \(T\): \[ Tax+Tby=\mathrm{gcd}(a,b)T. \] Now notice that \(ab|aT\) because \(a\) divides \(a\) and \(b\) divides \(T\); and also \(ab\) divides \(bT\) for the same sort of reason. Therefore we can factor \(ab\) out of \(Tax+Tby=abU\) and obtain \[ abU=\mathrm{gcd}(a,b)T. \] Finally we have \[ T=\frac{ab}{\mathrm{gcd}(a,b)}U. \] In other words, \(T\) isa multiple of \(ab/\mathrm{gcd}(a,b)\). This shows that any common multiple of \(a\) and \(b\) is a multiple of \(M=ab/\mathrm{gcd}(a,b)\), and is therefore greater than or equal to \(M\). Putting this together we see that \(M\) is a common multiple that is smaller than or equal to any other common multiple, and it is therefore \(\mathrm{lcm}(a,b)\).