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
!