Suppose we have two integers, and we’d like to find their greatest common divisor (GCD). Recall that the greatest common divisor of two integers m and n is exactly that: the greatest integer which is a divisor of both m and n. The obvious way to do this—which is probably the way you learned in elementary school, when reducing fractions—is to factor each integer into primes, and look for overlap. For example, let’s say we want to find the GCD of 450 and 525. We begin by factoring:

Now we pull out as many prime factors as we can which are contained in the factorizations of both numbers. We can’t use 2 at all, since it is only contained in the factorization of 450; we can use a factor of 3, but only one; and we can use two factors of 5. Putting these together, the greatest common divisor of 450 and 525 is .

This method is intuitive, and works well for relatively small numbers, but (there’s always a “but”, isn’t there?) it fails horribly for larger numbers. For example, what if you wanted to find the GCD of 2257394839 and 45466644967? (Go ahead, try it! =) The problem is that factoring is hard, even for computers—where by “hard” I mean “hard to do quickly”. It’s easy to write computer programs to do factoring, it’s just that no one knows how to write a program which factors large numbers quickly. (By “large” in this context I mean numbers with hundreds of digits; the two numbers I gave as an example above could be factored very quickly by a computer, but I bet YOU can’t factor them quickly, so the point is the same.)

Well, as you probably guessed, there’s a better algorithm for calculating the GCD of two numbers, since the GCD can actually be found without any reference to factorizations. This better algorithm is called the Euclidean Algorithm, in honor of Euclid, the first mathematician to write it down (around 300 BC, making it one of the oldest algorithms known!). It’s based on the property I showed (and proved) in my last post, namely, that

.

(Technically, in my last post I showed that , but since anything that divides x also divides -x, we can flip around the m-n if we want: anything that divides m-n will also divide -(m-n) = n-m, and vice versa.) Here’s how it works:

1. Given two integers m and n, if they are the same, then clearly they are equal to their greatest common divisor.
2. Otherwise, reduce the larger of the two numbers by subtracting the smaller number from it.
3. Lather, rinse, repeat.

That’s it. Were you expecting something more complicated? We already know that doing the subtraction step doesn’t change the GCD, and since the numbers are always getting smaller, the algorithm must eventually stop. Genius! That Euclid was one smart dude. Anyway, let’s try it on a simple example: finding the GCD of 56 and 20.

1. 56 is greater than 20, so subtract 20 from 56, leaving 36 and 20.
2. 36 is still greater than 20, so subtract 20 again, leaving 16 and 20.
3. Subtract 16 from 20, leaving 4 and 16.
4. Subtract 4 from 16 three times, eventually leaving 4 and 4.
5. Hence the GCD of 56 and 20 is 4! (This is easy to verify by factoring.)

Neat! But… what has all this got to do with the Calkin-Wilf tree? Well, if you haven’t already noticed, the Euclidean algorithm is exactly the same as the method for finding your way “up” the Calkin-Wilf tree! In particular, since all the rationals in the Calkin-Wilf tree are in lowest terms, finding your way up the Calkin-Wilf tree from m/n exactly corresponds to using the Euclidean Algorithm on m and n in order to show that their GCD really is 1. And in general, if , running the Euclidean Algorithm on m and n is like finding your way up a Calkin-Wilf tree in which all the numbers have been multiplied by d (so that it starts at d/d instead of 1/1). In an important sense, we can say that the Calkin-Wilf tree is the Euclidean Algorithm, in tree form!

In closing, I should note that in practice there’s a slight improvement we can make upon the basic Euclidean Algorithm. To see what it is, consider running the Euclidean Algorithm on 20451 and 2. Well, 20451 is bigger than 2, so subtract 2 from 20451, leaving 20449 and 2. Subtract 2 again, leaving 20447 and 2. 20447 is still bigger than 2, so subtract… this is the point where we start getting very bored. Everyone can see perfectly well that since 20451 is odd, after subtracting 2 enough times, we will eventually be left with 1. So this suggests our practical improvement: at each step, instead of replacing the larger number by the remainder when subtracting the smaller number, replace it by the remainder when dividing it by the smaller number—since division can be viewed as repeated subtraction. Now, using this improved method, can you find the GCD of 2257394839 and 45466644967?