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.
No comments:
Post a Comment