Sunday, April 15, 2018

elementary number theory - 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.

No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...