I am trying to learn the logic behind the Extended Euclidean Algorithm and I am having a really difficult time understanding all the online tutorials and videos out there. To make it clear, though, I understand the regular Euclidean Algorithm just fine. This is my reasoning for why it works:
If g=gcd(a,b), then gi=a and gj=b with gcd(i,j)=1. If you subtract the equations, then g(i−j)=a−b, which means g divides a−b too.
This implies that gcd(a,b)=gcd(a−kb,b) and so the maximum k is a−kb=0 or a=kb or ⌊a/b⌋=k, and the value of a−⌊a/b⌋b is the same as a mod b.
But I do not understand the Extended algorithm or the Identity.
Why is there always an x,y such that ax+by=gcd(a,b) for nonzero (positive?) a,b? I don't understand the intuition behind this claim.
I also don't understand how the Extended Euclidean algorithm works at all. Is it correct to say that the Extended Euclidean algorithm is what solves Bezout's Identity? It returns nonzero (positive?) x,y such that ax+by=gcd(a,b)?
Is the idea behind modular inverses included here too? If I want to solve for the inverse of a modulo m then this is the same as solving for x in ax=1modm for known integers a,m, the same as ax=1−my, the same as ax+my=1, so this is like using the Extended algorithm on a,m and checking if the gcd is equal to 1. If so, then the answer is x. Is my understanding correct?
No comments:
Post a Comment