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?

  • 1
    $\begingroup$ proof. Also this has been asked before. $\endgroup$ – user61527 Feb 5 '14 at 1:51
  • $\begingroup$ As T. Bongers has said, this is called Bezout's identity, pretty well known with proofs. $\endgroup$ – qwr Feb 5 '14 at 1:55
  • $\begingroup$ There can't be a smaller one, for if $xa+yb$ is say $m\gt 0$, then $d$ divides $m$, so $m\ge d$. $\endgroup$ – André Nicolas Feb 5 '14 at 2:04
  • $\begingroup$ 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). $\endgroup$ – WhizKid Feb 5 '14 at 2:10
  • $\begingroup$ @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? $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.