Extended Euclidean Algorithm: why does it work?

Question

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.

Answer 1

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

Answer

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?!

Answer 2

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}<b_n$ 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.$$