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. 

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
