Proof of Bezout's Lemma using Euclid's Algorithm backwards 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. 

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.


*First you have to accept:
Given an integer $x$, you can find the only integer y that satisfies the equation below:
$x + y = 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$



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



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



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