# Greatest common divisor is the smallest positive number that can be written as $sa+tb$

We know that $d = \gcd(a, b)$ can be written as $sa + tb$, where $s, t \in \mathbb{Z}$. Apparently, $d$ is the smallest positive number that can be written in this form. Why is this so?

• proof. Also this has been asked before. – user61527 Feb 5 '14 at 1:51
• As T. Bongers has said, this is called Bezout's identity, pretty well known with proofs. – qwr Feb 5 '14 at 1:55
• There can't be a smaller one, for if $xa+yb$ is say $m\gt 0$, then $d$ divides $m$, so $m\ge d$. – André Nicolas Feb 5 '14 at 2:04
• Bezout's theorem, you need to proof that the smallest positive integer written as a linear combination of a and b is in actual fact the highest common factor (the idea is to use divisibility). – WhizKid Feb 5 '14 at 2:10
• @AndréNicolas that is the simplest explanation I've seen! Thanks! Edit: actually, how do we know that m does not divide a and b and thus m itself is not the gcd of a and b? – Trent Bing Feb 5 '14 at 2:30

Here is a conceptual way to prove Bezout's gcd Identity. The set $\rm\,S\,$ of all integers of the form $\rm\,a\,x + b\,y,\,\ x,y\in \mathbb Z,\,$ is closed under subtraction $\ ax+by-(a\bar x+b\bar y)\, =\, a(x\!-\bar x)+b(y\!-\!\bar y).\,$ By the Lemma below, every positive $\rm\,n\in S\,$ is divisible by $\rm\,d =$ least positive $\rm\in S.\,$ Therefore $\rm\,a,b\in S\,$ $\Rightarrow$ $\rm\,d\mid a,b,\,$ i.e. $\rm\,d\,$ is a common divisor of $\rm\,a,b,\,$ necessarily the greatest common divisor by $\rm\ c\mid a,b\,$ $\Rightarrow$ $\rm\,c\mid d = a\,x_1\!+\! b\,y_1\Rightarrow$ $\rm\,c\le d.$

Lemma $\ \$ Let $\,\rm S\ne\emptyset \,$ be a set of integers $>0$ closed under subtraction $> 0,\,$ i.e. for all $\rm\,n,m\in S, \,$ $\rm\ n > m\ \Rightarrow\ n-m\, \in\, S.\,$ Then every element of $\rm\,S\,$ is a multiple of the least element $\rm\:\ell = \min\, S.$

Proof ${\bf\ 1}\,\$ If not there is a least nonmultiple $\rm\,n\in S,\,$ contra $\rm\,n-\ell \in S\,$ is a nonmultiple of $\rm\,\ell.$

Proof ${\bf\ 2}\,\rm\,\ \ S\,$ closed under subtraction $\rm\,\Rightarrow\,S\,$ closed under remainder (mod), when it is $\ne 0,$ since mod may be computed by repeated subtraction, i.e. $\rm\, a\ mod\ b\, =\, a - k b\, =\, a-b-b-\cdots -b.\,$ Thus $\rm\,n\in S\,$ $\Rightarrow$ $\rm\, (n\ mod\ \ell) = 0,\,$ else it is $\rm\,\in S\,$ and smaller than $\rm\,\ell,\,$ contra mimimality of $\rm\:\ell.$

Remark $\$ In a nutshell, two applications of induction yield the following inferences

$\ \ \rm\begin{eqnarray} S\ closed\ under\ {\bf subtraction} &\:\Rightarrow\:&\rm S\ closed\ under\ {\bf mod} = remainder = repeated\ subtraction \\ &\:\Rightarrow\:&\rm S\ closed\ under\ {\bf gcd} = repeated\ mod\ (Euclid's\ algorithm) \end{eqnarray}$

Interpreted constructively, this yields the extended Euclidean algorithm for the gcd. Namely,  starting from the two elements of $\rm\,S\,$ that we know: $\rm\ a \,=\, 1\cdot a + 0\cdot b,\ \ b \,=\, 0\cdot a + 1\cdot b,\$ we search for the least element of $\rm\,S\,$ by repeatedly subtracting elements of $\,\rm S\,$ to produce smaller elements of $\rm\,S\,$ (while keeping track of each elements linear representation in terms of $\rm\,a\,$ and $\rm\,b).\:$ This is essentially the subtractive form of the Euclidean algorithm (vs. mod/remainder form).

I think I've figured it out.

Suppose $\gcd(a, b) = m$ where $m \geq d$. By Bezout's identity $m$ can be written as $va + ub$.

Clearly $m | d$, implying $m \leq d$ since $m$, $d \geq 0$. Thus $m = d$.