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 is also useful to others!
Euclid's algorithm can be expressed in just a single line of python (assumes 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; the largest number which divides both any number and 0
is just that number. The recursive step requires a bit more explanation. For ease of explanation, consider the following diagram from 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)
? Let n
be such a quantity. What do we know about n
? Well, by definition n
divides both DC
and EA
. Because n
divides DC
, we can stack it to get up to a height of DC
. And because n
also divides EA
, we can stack it to get up to a height of EA
, which gets us all the way to BA
!