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:




