GCD and the magic of subtraction

The greatest common divisor is something I learned in school but it was one of those “so what?” subjects. But recently I revisited it and it is very interesting.

Why is gcd cool?

Every number, can be expressed as the product of prime numbers. This product for every number is unique; sort of like saying, every number has a fingerprint. This is called the fundamental theorem of arithmetic. 36 is 4x9, and 45 is 5x9. This means that some numbers will have common parts with each other.

These common parts can divide both numbers, and thus they are common divisors. In the example above, 36 is 4x9 or 2x2x3x3, while 45 is 5x3x3; 3 is a common divisor of both, so is 3x3, which is 9; but 9 is the greatest divisor of both 36 and 45.

One question I had when I was younger, was why we are talking about the “greatest” and not the smallest common divisor. We could, but soon, this gets boring: there is 1, the smallest common divisor of every number, then there are some common divisors in between 1 and the gcd. But what the gcd does so uniquely, is that it takes two numbers and gives us all the common parts of two numbers.

common and uncommon parts of 36(4×9) and 45(5×9). The gcd of 36 and 45 is 9.

This is cool! The uncommon parts are relatively prime! — meaning, they have nothing in common but the number 1.

So to find the gcd, then, we need to find all the common parts of the two numbers when written in terms of their prime factors.

36=3x3x2x2 and 45=3x3x5, thus the gcd of 36 and 45 is 3x3, which is 9. So 36 is 9(4) and 45 is 9(5). It is very interesting to look at numbers as multiples of gcds. Moreover, notice that these multipliers, 4 and 5 in the example above, are relatively prime.

The magic of subtraction

Subtracting two relatively prime numbers, will produce another number that, while not necessarily prime itself, will be relatively prime to both the previous numbers. As an example, 13-7=6. 6 is not prime, but it is relatively prime to both 7 and 13. If we subtract 6 from 13 we will get 7 again which is not very interesting. But if we subtract 6 from 7, the smaller one, since 6 and 7 are relatively prime we should get another number that is relatively prime to them both; 7-6=1, which is relatively prime to every other number, if keep doing this:

13 -  7 = 6
7  -  6 = 1
6  -  1 = 5
5  -  1 = 4
4  -  1 = 3
3  -  1 = 2
2  -  1 = 1
1  -  1 = 0

(1, 0)

The final two numbers are 0 and 1. So whenever we start with two relatively prime numbers and do this on them, it will always end with 0 and 1. This is pretty strange and magical. I am still perplexed by it, but the way I convinced myself, is to think about it bottom up: if we start with the number 1, and try to build our way to any other number by addition, there are finite number of ways. So when we start subtracting, what we are doing is walking that path backwards towards 1.

There is a limited set of paths from any two numbers back to 1 by successive subtractions.

Now why do these two numbers need to be relatively prime? because if they are not relatively prime, that means that they have some parts in common, like 36 and 45 above, remember? they are 9(4) and 9(5). If we do the subtracting trick on them:

9(5) - 9(4) = 9(1)
9(4) - 9(1) = 9(3)
9(3) - 9(1) = 9(2)
9(2) - 9(1) = 9(1)
9(1) - 9(1) = 9(0)

(9(1), 0)

So you see, the common part survives the subtractions, while the uncommon parts converge to 1. But 9 is all the common parts of 36 and 45, in other words the gcd of 36 and 45!

Can we keep subtracting any two numbers until we reach (X, 0) and then proclaim X is the greatest common divisor? yes, we can, and it is called the Euclidean Algorithm.

Here is a silly experiment, what if we subtract the partially common parts? for 36 and 45, what if we wrote them as 3(12) and 3(15)?

3(15) -  3(12) = 3(3)
3(12) -  3(3)  = 3(9)
3(9)  -  3(3)  = 3(6)
3(6)  -  3(3)  = 3(3)
3(3)  -  3(3)  = 3(0)

(3(3), 0)

This is really funny. The algorithm basically told us that the gcd of 12 and 15 is 3. Now if we choose to multiply the other 3 that we have factored out before we started our subtraction, it will yield the same result: the gcd of 36 and 45 is 9.

What just happened?

We started by finding the gcd of two numbers, then subtracting the uncommon, relatively prime parts to realize we always reach 1, so if we always subtract any two numbers from each other repeatedly, since the gcd is a common factor of both, it will remain constant until the end, when the uncommon parts have reduced down to 1 and 0; and then what we are left with is the gcd.

Here is a recursive implementation of it in Python:

def gcd(a,b):
    if a == 0: return b
    if b == 0: return a

    return gcd(abs(a-b), min(a,b))

If someone has a better explanation of why subtracting relatively prime numbers repeatedly will always result in one, please leave a comment or reach out and help me understand better.