Proof of Bezout's Lemma using Euclid's Algorithm backwards

Question

I've seen it said that you can prove Bezout's Identity using Euclid's algorithm backwards, but I've searched google and cannot find such a proof anywhere. I found another proof which looks simple but which I don't understand.

Bezout's lemma is:

For every pair of integers a & b there are 2 integers s & t such that as + bt = gcd(a,b)

Euclid's algorithm is:

1. Start with (a,b) such that a >= b
2. Take reminder r of a/b
3. Set a := b, b := r so that a >= b
4. Repeat until b = 0

So here's the proof by induction that I found on the internet:

Base case:

b = 0 
gcd (a,b) = a
s = 1 
t = 0

Inductive Step:

Assume Bezout's Lemma is true for all pairs of b < k.

a = qb + r with 0 =< r < b = k

gcd (a,b) = gcd (b,r)

By the inductive hypothesis there are integers x and y with bx and ry = gcd(a,b)

bx + ry = bx + (a - qb)y = b(x - qy) + ay = gcd(a,b)

Set t = (x - qy) and s = y. This establishes the identity for a pair (a,b) with b = k and completes the induction. 

I only followed the proof up to the base case. I don't see how it proved b = k from b < k. Could you please explain this to me?

Thanks.

EDIT: After two days of trying to figure it out I still don't understand the proof. I conclude that either I lack the requisite knowledge or the intelligence or both. Thanks for trying to help.

Answer 1

Below is a simple conceptual proof of Bezout's identity for the gcd.

The set $\rm\:S\:$ of all integers of form $\rm\:a\:x + b\:y,\,\ x,y\in \mathbb Z,\:$ is closed under subtraction 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\:|\:a,b.\:$ Thus $\rm\:d\:$ is a common divisor of $\rm\:a,b,\:$ necessarily greatest, $ $ by $\rm\:c\:|\:a,b\:$ $\Rightarrow$ $\rm\:c\:|\:d = a\:x\!+\! b\:y\:$ $\Rightarrow$ $\rm\:c\le d.$

Lemma $\ $ If a nonempty set of positive integers $\rm\: S\:$ satisfies both $\rm\ n > m\: \in\, S \ \Rightarrow\ n-m\, \in\, S$
then every element of $\rm\:S\:$ is a multiple of the least element $\rm\:m_{\circ} \in\, S.$

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

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.\:$ Hence $\rm\:n\in S\:$ $\Rightarrow$ $\rm\: n\ mod\ m_\circ = 0,\:$ else it is $\rm\,\in S\,$ and smaller than $\rm\:m_\circ\,$ contra mimimality of $\rm\:m_\circ$

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

$$\!\rm\begin{eqnarray} S\ closed\ under\ subtraction &\!\Rightarrow\:&\rm S\ closed\ under\ mod \!=\! remainder = repeated\ subtraction \\ &\!\Rightarrow\:&\rm S\ closed\ under\ gcd\! =\! repeated\ remainder\!\!: 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 to produce smaller elements of $\rm\,S\,$ (while keeping track of every elements linear representation in terms of $\rm\,a\,$ and $\rm\,b).\:$ This is essentially the subtractive form of the Euclidean algorithm (vs. the mod/remainder form).

Answer 2

The idea you allude to is doing euclids algorithm to find the gcd, then back substituting all the way to get the values to plug into the bezout equation.

Actually this is a waste of time, you can do both simultaneously! This is called Blankenship's algorithm

You can read about it here http://mathworld.wolfram.com/BlankinshipAlgorithm.htm

Answer 3

This is not a rigorous proof, but it can help you understand how induction works.

I will try to explain all this naturally like I am exploring unknown things.

0. First you have to accept: Given an integer $x$, you can find the only integer y that satisfies the equation below: $x + y = 1$

---

1. As you said:

$a = q*b + r$ with $0 =< r < b $

$\gcd (a,b) = \gcd (b,r)$. let $a_0=a,b_0=b; a_1=b, b_1=r ... $

and let $a_i = q_i*b_i + b_{i+1}$

finally, you can get the successive equations:

$a_0 = q_0*b_0 + b_1$

$a_1 = q_1*b_1 + b_2$

...

$a_{n-1} = q_{n-1}*b_{n-1}+b_n$, where $b_n = 0$

$a_n = q_n*b_n + b_{n+1}$,

so $\gcd(a_0, b_0) = ... = \gcd(a_n, b_n) = a_n$

---

2. Naturally thinking

the first part of bezout lemma (what we want to prove): $a*s + b*t = \gcd(a, b)$

assume there are two integers $s_{n-1}, t_{n-1}$, make the equation (1) true:

$s_{n-1}a_{n-1} + t_{n-1}b_{n-1} = \gcd(a,b) = a_n$ ... (1)

and we know $a_{n-1} = q_{n-1}b_{n-1}+b_n$, $b_{n-1}=a_n, b_n = 0$

so equation (1) can be expressed as:

$s_{n-1}q_{n-1}a_n + t_{n-1}a_n = \gcd(a,b) = a_n$

that is $s_{n-1}q_{n-1} + t_{n-1} = 1$

for a fixed $s_{n-1}$, $ \quad t_{n-1}$ always exists to make (1) true

do the same things on:

$ s_{n-2}a_{n-2} + t_{n-2}b_{n-2} = \gcd(a,b) = a_n $

...

you will finally get: $(s_{n-2}q_{n-2} + t_{n-2})q_{n-1}+s_{n-2} = 1$

such $s_{n-2} $ and $ t_{n-2}$ must exist.

---

3. by induction

all equations like $s_{i}a_{i}+t_{i}b_{i} = gcd(a, b)$ can be finally transfered to equations with $a_n$, $b_n$, (many quotients) $q_{i}$, $s_{i}$ and $t_{i}$

Finally, either $s_i$ or $t_i$ appears at the end of the equation.

while $a_n$ could be eliminated, and $b_{n}=0$

everything goes back to $x + y = 1$, where $x$ is fixed.

---

4. proof

you can find the proof here

https://personal.math.ubc.ca/~marcus/Math342/euclid.pdf

The second part of bezout lemma: gcd(a, b) is the smallest positive integer of the form as + bt.

I believe that proving the second part of bezout lemma is just a piece of cake for you.