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 $\lfloor a/b \rfloor = k$, and the value of $a-\lfloor a/b \rfloor 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 = 1 \bmod m$ 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?
Best Answer
An example how the extended algorithm works :
$a=77$ , $b=21$
We have $$77=3\times 21+14$$
$$21=1\times 14+7$$
$$14=2\times 7$$
$7$ is the gcd of $77$ and $21$.
Now we calculate backwards : $$7=21-14=21-(77-3\times 21)=4\times 21-77$$ to get the desired representation.
This backwards-method always works. Another example
$a=38$ , $b=25$
$$38=1\times 25+13$$
$$25=1\times 13+12$$
$$13=1\times 12+1$$
$$12=12\times 1$$
So, we have
$$1=13-12=13-(25-13)=2\times 13-25$$