2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I don't understand the "calculate backwards" part or why it's being done this way? $\endgroup$ – Aruka J Jan 10 '16 at 21:40
0
$\begingroup$
  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$):enter image description here

$\endgroup$
0
$\begingroup$
  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$.

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

  2. Yes.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.