Bezout's Identity proof and the Extended Euclidean Algorithm

Question

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.

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

2. 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)$?

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

Answer 1

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$$

Answer 2

1. Always that $a\neq 0$ or $b\neq 0$ then $g=gcd(a,b)$ exist. Furthermore, $g=ma+nb$ for $m,n\in\mathbb{Z}$.

   Indeed, let $\Sigma=\{ma+nb:ma+nb>0, m,n\in\mathbb{Z}\}$. For all $m,n\in\mathbb{Z}$ such that $ma+nb\neq 0$, if $ma+nb>0$, $ma+nb\in\Sigma$; if $ma+nb<0$ then $-(ma+nb)=(-m)a+(-n)b>0$, i.e, $(-m)a+(-n)b\in\Sigma$. How $\Sigma\neq\emptyset$ and $\Sigma\subseteq\mathbb{N}$, $\Sigma$ admits a minimal element $d=m_{0}a+n_{0}b$. We will proof that $g=d$.

   If $c|a$ and $c|b$ then $c|m_{0}a$ and $c|n_{0}b$; therefore $c|d$. Now, note that $a,b\in\Sigma$: $a=1a+0b$, $b=0a+1b$. Applying the Euclidean algorithm: $a=qd+r$, $0\leq r<d$. Then $$a=q(m_{0}a+n_{0}b)+r ,$$ so, $r=(1-qm_{0})a+(-qn_{0})b.$ Since $r\notin\Sigma$, we have $r=0$. It follows that $d|a$. Similarly, $d|b$. We proved that $d=g$.

gcd can be defined as the smallest integer linear combination of $a$ and $b$.

2. The idea of Extended Euclidean algorithm is to express each of the residues obtained after division in terms of $a$ and $b$ in a similar manner of the formula $d=m_{0}a+n_{0}b$.

3. Yes.

Answer 3

1. There exist such $x$ and $y$ because at each step of the E.E.A. the remainder has the same property. It can be proved by induction, starting with $a=1\cdot a+0\cdot b$, $\enspace b=0\cdot a+1\cdot b$.
2. $x$ and $y$ of opposite signs.
3. is correct.

Here is a layout for the E.E.A. ($\gcd(133,99$):