4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ $\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))$ $\endgroup$ – Matthew Towers Mar 18 '20 at 10:16
12
$\begingroup$

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

GCD example

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

enter image description here

Answer

enter image description here

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

enter image description here

Pretty cool, huh?!

$\endgroup$
3
  • $\begingroup$ This is beautiful, and makes so much sense. Thank you! $\endgroup$ – John P. Mar 18 '20 at 2:03
  • $\begingroup$ Euclid not Euler. $\endgroup$ – Somos Mar 18 '20 at 2:38
  • 4
    $\begingroup$ 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! $\endgroup$ – David G. Stork Mar 18 '20 at 3:02
3
$\begingroup$

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

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