## The gcd as the smallest positive linear combination

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)$$.

## The relationship between lcm and gcd

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)$$.