Visual intuition for the Euclidean algorithm

I have a broader goal of demystifying cryptocurrency, and making it generally useful for ordinary people to do ordinary non-criminal commerce with it.

Part of that is improving tooling, and part of that is making the theoretical underbelly of cryptography and cryptocurrency more accessible. Here’s the thing: none of this is complicated. All of it is simple. There’s just a lot. A large volume of simple ideas tends to manifest to an outsider as complexity.

However, humans are very stupid. We can’t handle ideas that are genuinely complex.

The mathematical underbelly of cryptography is a field called "number theory". Number theory is what mathematicians call arithmetic, but if you call it arithmetic, your grant proposal gets denied. So it’s called "number theory".

All of number theory rests on the GCD algorithm, more often called the "Euclidean algorithm". That’s what I want to explain to you today.

There’s explanations elsewhere (I particularly like this one) about how to code the GCD algorithm, as well as some justification about why it converges to the GCD etc. Not what I’m interested in today. I want to give you some intuition.

Visually you can envision the Euclidean algorithm as solving the following problem: given two line segments, find the biggest line segment which cleanly divides both.

Let me use the example of finding the GCD of 210 and 45, which I am copying from this website

We have two segments which are of length 210 and 45:

We can replicate the length 45 segment 4 times to get a segment of length 180. If we replicated it again, we would get a segment of length 225, which is bigger than 210:

The number of times we replicate it (4) is called the quotient, and the length of the remaining segment (30) is called the remainder.

The key observation is as follows:

Any segment that cleanly divides the original two segments also cleanly divides the remainder.

Visually this is obvious. It is also obvious algebraically. If our original two numbers are A and B, then

A = q*B + r

r = A - q*B

where q is the quotient and r is the remainder. Any number that cleanly divides A and B also cleanly divides A - q*B, and by algebra, also divides r.

The central idea of the Euclidean Algorithm is to reduce the problem to finding the GCD of B and r, recursively, until we get to an answer. We get to an answer when the remainder r is 0:

That’s it.

I can explain it to you algebraically a billion times and give you all the theoretical justification in the world, but nothing works as well as a simple picture. If you just remember (or reference) that picture, it should be pretty intuitive about how this works, how to code it, and most importantly, why it works.

An important question to ask is is this algorithm guaranteed to terminate?, to which the answer is yes, and there’s a billion algebraic explanations of why that you can find online. I’ll leave it as an exercise to you to find an intuitive explanation of why.

As a hint, the case where it would not terminate would be if the two segments were not integer multiples of a single segment. But since we’re dealing with integers (all of which are multiples of 1), this is not a situation we have to worry about.

This also should make clear that whether the integers are postive or negative plays no essential role. All positive/negative does is impose a directionality (left/right arrowness) on the segments. This is a completely orthogonal concern to finding a segment that cleanly divides them.

The only tricky case is finding the GCD of a nonzero number with 0, and that is a math technicality: every number divides 0. So gcd(A, 0) = A for all A, including A = 0.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.