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