# Extended Euclidean Algorithm: why does it work?

I find myself able to mechanically apply the "extended" Euclidean algorithm to find the gcd of two integers and to write a linear combination by working backwards. However, I do not have a good grasp as to why this works. Artin gives a paragraph-long explanation of it, but I am not able to follow it, nor do I have any good intuition for why this process works.

One can compute a greatest common divisor easily by repeated division with remainder. For example, if $$a = 314$$ and $$b = 136$$, then $$314 = 2 \cdot 136 + 42, \; 136 = 3 \cdot 42 + 10, \; 42 = 4 \cdot 10 + 2.$$ Using the first of these equations, one can show that any integer combination of $$314$$ and $$136$$ can also be written as an integer combination of $$136$$ and the remainder $$42$$, and vice versa. So $$\mathbb{Z}(314) + \mathbb{Z}(136) = \mathbb{Z}(136) + \mathbb{Z}(42)$$, and therefore $$\gcd(314, 136) = \gcd(136, 42)$$. Similarly, $$\gcd(136, 52) = \gcd(42,10) = \gcd(10,2) = 2$$. So the greatest common divisor of $$314$$ and $$136$$ is $$2$$. This iterative method of finding the greatest common divisor of two integers is called the Euclidean Algorithm.

I'm fine with the first line. If I have an integer combination $$314x + 136y,$$ I can use the first given equation to write instead $$314x + 136y = (2 \cdot 136 + 42)x + 136y = 2x \cdot 136 + 42x + 136y = (2x+y) \cdot 136 + 42x.$$ I can then write $$136$$ in terms of $$42$$ and $$10$$ and get a linear combination of $$42$$ and $$10$$, and so forth, and since the integers are closed, my coefficients will always be integers, so I end up with another integer combination.

I cannot understand anything beyond this point in the text, though. I do not know what Artin means by the notation $$\mathbb{Z}(314)$$. Further, I have no intuition for why the $$\gcd$$ remains constant all the way down the chain or, even, why the last remaining, non-zero remainder in the algorithm is the $$\gcd$$.

Any help with the intuition would be greatly appreciated.

• $\mathbb{Z}(314)$ means "the ideal of $\mathbb{Z}$ generated by 314". The reason to introduce it is that $\mathbb{Z}(a) + \mathbb{Z}(b) = \mathbb{Z}(\gcd(a,b))$ – Matthew Towers Mar 18 '20 at 10:16

Consider the $$GCD(9,30)$$. Make a grid of width $$9$$ cells and height $$30$$ cells.

Now fill in squares of dimension $$9 \times 9$$, starting at the bottom. If they fill the entire grid, then $$9$$ divides the larger number, and is the GCD. For instance, if we were interested in $$GCD(9, 27)$$ then the $$9 \times 9$$ squares would fill the array and $$9$$ would (of course) be the $$GCD(9,27)$$.

But in our case they do not. There is a $$9 \times 3$$ strip (white) across the top--the remainder. Thus $$GCD(9,30) \neq 9$$.

Consider that strip. It is of height $$3$$.

So the Euclid algorithm says (in effect) "try tiling the white band with $$3 \times 3$$ squares." Can we do that? YES! Thus $$3$$ divides the "white remainder" as well as the width $$9$$ of the earlier squares. Thus $$3$$ divides both $$9$$ as well as $$30$$. Why? It divides the white band ($$3$$) and each big square ($$9$$); thus it divides $$30$$. (In other words, $$3$$ divides $$3$$, it divides $$9$$, and thus it divides any multiple of $$9$$... thus it divides their sum: $$3 + 9 + 9 + 9 = 30$$.)

Thus $$GCD(9,30) = 3$$.

If the $$3$$ happened not to divide the top (white) band, then there would be a remainder (column). Iterate the procedure to find a new (smaller) value that tiles that remainder column, which then tiles the white band, which then also tiles the larger number.

Try it yourself!

Use this figure to find the $$GCD(8, 22)$$:

Do you see how $$GCD(8,22)=2$$?

Just for fun I illustrated the problem posed by the OP. (I rotated the figure $$90^\circ$$ so it would fit here.) It is hard to see, but the white remainder column is of dimensions $$10 \times 2$$, so indeed $$GCD(136,314) = 2$$.

Pretty cool, huh?!

• This is beautiful, and makes so much sense. Thank you! – John P. Mar 18 '20 at 2:03
• Euclid not Euler. – Somos Mar 18 '20 at 2:38
• I know... when I first learned this I was so glad to see how all that abstract symbol manipulation could be viewed graphically. If you're like me, you'll never forget the Euclid Extended Algorithm! – David G. Stork Mar 18 '20 at 3:02

Start with vectors $$A_0:=(a,1,0)$$, $$B_0:=(b,0,1)$$. We want to find the $$\gcd$$ of the first component. Certainly, the gcd doe not change if we swap $$A$$ and $$B$$ or subtract and integer multiple of one vector from the other. Hence if we performm

Given $$A_n=(a_n,c_n,y_n)$$ and $$B_n=(b_n,u_nv_n)$$ with $$a_n\ge 0$$ and $$b_n>0$$, let $$q=\lfloor \frac {a_n}{b_n}\rfloor$$ and then $$A_{n+1}=B_n$$, $$B_{n+1}=A_n-qB_n$$

then we have $$\gcd(a_{n+1},b_{n+1})=\gcd(a_n,b_n\}=\ldots =\gcd(a,b)$$. Also, $$0\le b_{n+1} so that after finitely many steps we reach $$v_n=0$$, i.e., $$A_n=(d,x,y), B_n=(0,u,v)$$ where $$d=\gcd(d,0)=\ldots=\gcd(a,b)$$ and from the book-keeping extra coordinates, we read off that $$A_n=xA_0+yB_0,\quad B_n=uA_0+vB_0,$$ in particular, $$\gcd(a,b)=xa+yb.$$