Every time I use Euclid's algorithm, I have to re-convince myself why it works. This blog post will provide an explanation of Euclid's algorithm so I can refer back to it in the future. Hopefully it will also be useful for others!

Euclid's algorithm can be expressed in just a single line of python (assuming b >= a):

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

The base case of this algorithm is quite reasonable; it says the largest number which divides both any number and 0 is just that number. The recursive step requires a bit more explanation, however. For ease of explanation, consider the following diagram (courtesy of wikipedia):

Say we are interested in computing gcd(BA, DC). One very helpful way to think about recursion is as a black box. What if we had gcd(DC, EA)? Could we use it to compute gcd(BA, DC)?

As an aside, we can think of a number b dividing a as being able to "stack" columns of length b to reach a height of exactly a.

Let n = gcd(DC, EA). What do we know about n? Well, by definition n divides both DC and EA (and is the largest such number that does so). Because n divides DC, we can stack multiple copies of n to get up to a height of exactly DC. n also divides EA, which is exactly how much height remains to reach BA. Hence we can continue the stack to get all the way up to BA. Therefore n dividing DC and EA implies n divides BA!