Every time I use Euclid's algorithm, I have to reconvince myself why it works. Hopefully I'll be able to refer back to this blog post in the future.

The entirety of Euclid's algorithm is as follows (assumes b >= a):

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

The base case of this algorithm is quite reasonable; the gcd of a number and 0 is just that number. The recursive step requires a bit more explanation.

One helpful way to think about recursion is as a black box. What if we had the gcd of b and a % b? How could be use it to compute the gcd of a and b? Well if we know the gcd of b and a % b, then that must be the gcd or a and b! Why is this the case? Well it's because the gcd of b and a % b is the largest such number that divides both b and the "difference" between b and a. Since this number is the gcd of b and a % b, it certainly divides b. Given that this number also divides a % b, how is this helpful? Well since this number divides b, we can think of repeating this number to get up to b. Then since the number divides a % b, we can keep repeating the number to fill in the difference. Hence the number divides both a and b!

The picture that was most helpful for my understand is from wikipedia: