Intuitive Understanding of GCD algorithm

Question

What's an intuitive way to understand how this algorithm finds the GCD?

function gcd(a, b) {
    while (a != b)
        if (a, b)
            a -= b;
        else
            b -= a;
    return a;
}

Answer 1

My intuition for this particular algorithm is a composite of propositions in which I deeply believe and from them arises the general feeling of understanding the whole.

1. If both numbers are equal then any one of them is gcd.
2. What is the next trivial situation that's a bit harder than the previous one?
   If a + a = b then a is the gcd (think about this one).
3. If we subtract small quantity from a then we break gcdness property of a: a + (a - r) = b and we have to consider some other candidate for gcd that is smaller (!) than a.
4. And the final thought that seals the deal for me. The b was an impostor and it was a all along! a + (a - r) = a + a. So we don't care about b at all now. We want to find how to cover with gcd both a and (a - r). Recall that (a - r) is a smallified a. Now we need to find some number which is smaller than a that covers both a and (a - r). Notice the word covers in my last sentence. This is the intuitive word, the action I imagine happening in my brain. I imagine like paving slabs filling in the gaps on the road.

I tend to forget this algorithm quite often and then I go though this exercise in my head by going through this list ascending from most trivial propositions to less trivial statements and then as I go higher my brain fills in the next step and the next step and eventually Aha! I get it! The whole thing clicks.

It's also important to understand that intuition is not linguistic. Meaning, you cannot just read these sentences and memorise them and then declare that you understood. You cannot replace true understanding with words or formulas. What really has to happen is that you have to operate on images in your brain as you read the words in this answer (image in the brain is not 2D picture made out of pixels you see on the screen - it is more of an all-encompassing feeling). The algorithm is a change in time. So in the end you have to produce a personalised animation in your head that totally and completely makes sense to you. Watching existing animations for the algorithm might help to create your own internal animation, but they should only be used as a guidance and not for memoization. Intuition is a personal animation that targets your particular brain structure and composition of thoughts and ideas, belief structures that you already have. You cannot fake or cheat intuition by memorising stuff. The formulas that people use like a = bq + r are not intuition also. They are just compressed english language to communicate information about restrictions on the space of possibilities and you need to construct a personalised image from this communication message.

Answer 2

The original inventor of the greatest common divisor algorithm was Euclid, who described it in his book Elements about 300 years before the birth of Christ. Here is his geometric explanation, including his diagram:

Let AB and CD be the two given numbers not relatively prime.

It is required to find the greatest common measure of AB and CD.

If now CD measures AB, since it also measures itself, then CD is a common measure of CD and AB. And it is clear that it is also the greatest, for no greater number than CD measures CD.

But, if CD does not measure AB, then, when the less of the numbers AB and CD being continually subtracted from the greater, some number is left which measures the one before it.

For a unit is not left, otherwise AB and CD would be relatively prime, which is contrary to the hypothesis.

Therefore some number is left which measures the one before it.

Now let CD, measuring BE, leave EA less than itself, let EA, measuring DF, leave FC less than itself, and let CF measure AE.

Since then, CF measures AE, and AE measures DF, therefore CF also measures DF. But it measures itself, therefore it also measures the whole CD.

But CD measures BE, therefore CF also measures BE. And it also measures EA, therefore it measures the whole BA.

But it also measures CD, therefore CF measures AB and CD. Therefore CF is a common measure of AB and CD.

I say next that it is also the greatest.

If CF is not the greatest common measure of AB and CD, then some number G, which is greater than CF, measures the numbers AB and CD.

Now, since G measures CD, and CD measures BE, therefore G also measures BE. But it also measures the whole BA, therefore it measures the remainder AE.

But AE measures DF, therefore G also measures DF. And it measures the whole DC, therefore it also measures the remainder CF, that is, the greater measures the less, which is impossible.

Therefore no number which is greater than CF measures the numbers AB and CD. Therefore CF is the greatest common measure of AB and CD.

Observe that Euclid uses the word "measures" to indicate that some multiple of a smaller length is the same as a larger length; that is, his concept "measures" is identical to our concept "divides" as in 7 divides 28.

Answer 3

In short, if both a and b is dividable by a D then it has to be a divisor of a-b and can not be bigger than a-b. The logic is to apply this recursively with the addition of the rule that for a=b the GCD is a:

GCD(a, b) = a == b ? a : GCD(min(a, b), abs(a-b))

Answer 4

Wikipedia has a good article on it under the name Euclidean algorithm. In particular, this image from the article might answer your literal question: the intuitive way to understand how this algorithm finds GCD:

Subtraction-based animation of the Euclidean algorithm. The initial rectangle has dimensions a = 1071 and b = 462. Squares of size 462×462 are placed within it leaving a 462×147 rectangle. This rectangle is tiled with 147×147 squares until a 21×147 rectangle is left, which in turn is tiled with 21×21 squares, leaving no uncovered area. The smallest square size, 21, is the GCD of 1071 and 462.