Visualization for Euclidean Algorithm

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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