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 (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
(and is the largest such number that does so).
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
. 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 the remaining height, so we can continue our stack to get all the way up to BA
. Hence n
dividing DC
and EA
implies n
divides both DC
and BA
!
Hence gdc(DC, EA)
= gcd(BA, DC)
.