1

I want to really understand the Euclidean Algorithm.

A key component in the algorithm is fact that common divisors of two integers are common divisors of their difference.

I can see from the perspective of symbolic manipulation that for all common divisors of $a$ and $b$:

$d|a \land d|b$ means $a = kd \land b = ld \therefore a - b = kd - ld = (k - l)d$.

The trouble is, this doesn't convince me. I need am image or some way of grasping this beyond just the symbols.

The same for the rest of the algorithm. I get that the division/modulo version is really just applying subtraction multiple times, so understanding the subtraction part should help with that.

Then there is the issue of the last non-zero remainder being the GCD. Again, I can kind of understand via algebraic proof, but it's not convincing for me. I wouldn't bet much money on being able to convince an expert that I really understand.

So, any and all visual proofs, intuitions etc. that don't rely on that vertical list of divisors becoming dividends and remainders become divisors would be much appreciated.

J. W. Tanner
  • 60,406
Robin Andrews
  • 957
  • 1
    well, id $d|a$ and $d|b$, then you can imagine $a,b$ as collections of $d$-blocks. $a-b$ means removing $d$-blocks from $a$, so what's left is still a collection of $d$-blocks – Exodd Jul 05 '20 at 17:47
  • 1
    Maybe you can imagine the algorhitm as "cutting squares" from the initial rectangle $a\times b$ until you get the square $d\times d$.. – richrow Jul 05 '20 at 17:48
  • 1
    Give this a try: http://www.barmodelhost.com/sample/ – imranfat Jul 05 '20 at 17:48
  • Here: https://math.stackexchange.com/questions/3584894/extended-euclidean-algorithm-why-does-it-work/3584928#3584928 – David G. Stork Jul 05 '20 at 17:53
  • @Exodd any recommended shape for a d-block? Is a d by 1 strip of joined cubes a good way to visualize this? – Robin Andrews Jul 05 '20 at 21:12

3 Answers3

2

For myself I found useful to visualize the steps and the various parameters that comes into play by representing the Extended Euclidean Algorithm with the corresponding expansion into continued fraction, for instance $$ \eqalign{ & {{34} \over {13}} = \left\lfloor {{{34} \over {13}}} \right\rfloor + {8 \over {13}} = 2 + {1 \over {{{13} \over 8}}} = 2 + {1 \over {1 + {5 \over 8}}} = 2 + {1 \over {1 + {1 \over {{8 \over 5}}}}} = \cr & = 2 + {1 \over {1 + {1 \over {1 + {3 \over 5}}}}} = 2 + {1 \over {1 + {1 \over {1 + {1 \over {{5 \over 3}}}}}}} = 2 + {1 \over {1 + {1 \over {1 + {1 \over {1 + {1 \over {{3 \over 2}}}}}}}}} = \cr & = 2 + {1 \over {1 + {1 \over {1 + {1 \over {1 + {1 \over {1 + {1 \over 2}}}}}}}}} = 2 + {1 \over {1 + {1 \over {1 + {1 \over {1 + {1 \over {1 + {1 \over {1 + 1}}}}}}}}}} \cr} $$

G Cab
  • 35,272
0

If $d\mid a$, you can divide $a$ things into $d$ equal parts, and conversely. For instance, you can divide $a$ apples among $d$ children so that each child gets the same number of apples. Similarly, if $d\mid b$, you can divide $b$ apples among $d$ children so that each child gets the same number of apples.

Now suppose that you have $a+b$ apples and $d$ children among whom to distribute them. Split the apples into two piles, one with $a$ apples and the other with $b$ apples. You can hand out the apples in the first pile in such a way that each child gets the same number of apples, and then you can do the same thing with the second pile. Voilà! You have distributed all $a+b$ apples to the $d$ children, and each child has received the same number of apples: it must be that $d\mid a+b$.

Brian M. Scott
  • 616,228
0

Both numbers are multiples of the $\gcd$, let $g$, and obviously the difference of two multiples is again a multiple. Furthermore, if you consider the ratios $\dfrac ag,\dfrac bg$, they are integer and relative primes ($\gcd=1$).

So you can think of $a,b$ as two numbers with "granularity" $g$ and you combine them until you reach a single "grain". E.g. $a=42=7\cdot6,b=18=3\cdot6$. The ratios are $7,3$, leading to the sequence $7,3,4,1$ (corresponding to $42,18,24,6$).

With a different grain, say $5$, you would have the sequence $35,15,20,5$.

So the algorithm is equivalent to the reduction of two integers that are relative primes to a single unit (which you can't reduce further), by a sequence of decreasing differences (as the larger number is decreasing, you will always reach $1$).