# 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, 2014 at 1:51
• As T. Bongers has said, this is called Bezout's identity, pretty well known with proofs.
– qwr
Feb 5, 2014 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$. Feb 5, 2014 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). Feb 5, 2014 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? Feb 5, 2014 at 2:30

A conceptual proof of Bezout's gcd Identity: the set $$\rm\,S\,$$ of all integers of form $$\rm\,a\,x + b\,y,\,\ x,y\in \mathbb Z,\,$$ is $$\color{#c00}{\text{closed under subtraction}}$$ $$\rm\, ax+by-(a\bar x+b\bar y)\, =\, a(x\!-\bar x)+b(y\!-\!\bar y),\,$$ so by Lemma below, every positive $$\rm\,n\in S\,$$ is divisible by $$\rm\,d =$$ least positive $$\rm\in S.\,$$ So $$\rm\,a,b\in S\,$$ $$\Rightarrow$$ $$\rm\,d\mid a,b,\,$$ i.e. $$\rm\,d\,$$ is a common divisor of $$\rm\,a,b,\,$$ necessarily greatest such 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\,$$ $$\color{#c00}{\text{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 is computable 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}\rm 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).

Note: in more general numbers systems enjoying Division with Remainder (i.e. Euclidean domains) it is not true that $$\!\bmod\!$$ is equivalent to repeated subtraction, so in such rings the above descent is achieved by $$\!\bmod\!$$ (vs. subtraction), as in Proof $$2,\,$$ e.g. this is true for polynomial rings over a field.

The conceptual structure will be clarified when one studies ideals of rings, where the above proof generalizes to show that Euclidean domains are PIDs.

Beware  This linear representation of the the gcd need not hold true in all domains where gcds exist, e.g. in the domain $$\rm\:D = \mathbb Q[x,y]\:$$ of polynomials in $$\rm\:x,y\:$$ with rational coefficients we have $$\rm\:gcd(x,y) = 1\:$$ but there are no $$\rm\:f(x,y),\: g(x,y)\in D\:$$ such that $$\rm\:x\:f(x,y) + y\:g(x,y) = 1;\:$$ indeed, if so, then evaluating at $$\rm\:x = 0 = y\:$$ yields $$\:0 = 1.$$

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