2
$\begingroup$

Let $a,b, c$ belong to $\mathbb Z$ such that $(a,b,c) \neq (0,0,0)$. Define the [highest common factor] greatest common divisor ${\rm gcd}(a, b, c)$ to be the largest positive integer that divides $a, b$, and $c$.

Prove that there are integers $s, t, u$, such that $${\rm gcd}(a, b, c) = sa + tb + uc$$ Find such integers $s, t, u$ when $a = 91, b = 903, c = 1792$.

$\endgroup$
  • 1
    $\begingroup$ proofwiki.org/wiki/B%C3%A9zout's_Lemma $\endgroup$ – lab bhattacharjee Feb 26 '14 at 16:18
  • $\begingroup$ I found the Highest Common Factor which is 7, and now I think I should work backwards, but I don't know how to do it with 3 numbers $\endgroup$ – John Feb 26 '14 at 16:23
  • $\begingroup$ @John note that the "highest common factor" is named greatest common divisor and is denoted by ${\rm gcd}$. $\endgroup$ – AlexR Feb 26 '14 at 16:28
  • $\begingroup$ @John See the link in my answer to the extended Euclidean algorithm. The method describe their also works to compute the Bezout identity for three numbers (or any finite number). $\endgroup$ – Bill Dubuque Feb 26 '14 at 18:23
2
$\begingroup$

Below is one conceptual way to prove Bezout's Identity for the gcd = hcf. For computation of the Bezout identity it is convenient to employ the extended Euclidean algorithm.

The set $\rm\,S\,$ of integers of form $\rm\,a\,x + b\,y+c\,z,\,\ x,y,z\in \mathbb Z,\,$ is closed under subtraction so, by the 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,\,$ and greatest: $\rm\ c\mid a,b\,$ $\Rightarrow$ $\rm\,c\mid d = a\,x\!+\! b\,y\!+\!c\,z\,$ $\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).

$\endgroup$

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.