The Greatest Common Divisor (GCD) is the largest integer that evenly divides two numbers. For example:

gcd(10, 5) is 5
gcd(20, 8) is 4
gcd(9, 0) is 9

Euclid noticed an efficient pattern for solving this problem back in 300BC, which is known as Euclid’s algorithm. It is also an example of a recursive algorithm and therefore commonly taught alongside recursion in introductory computer science classes.

Here is the algorithm in pseudocode:

gcd(a, b) = a, if b = 0
          = gcd(b, a % b), otherwise

Note that % refers to the modulo operator which yields the remainder from the division of the first argument by the second. It does not represent simple division, which in Python is represented by the / operator.

If one of the numbers, b, is 0 then the other number a is the greatest common divisor since nothing can divide into 0. (We can see this in the third example above for gcd(9, 0).)

The key insight however comes in the second line: the gcd of two numbers does not change even if the larger number is replaced by its difference with the smaller number.

Therefore we can recursively compute the difference between the two numbers until they are equal, in which case the remainder is 0. Consider that 5 / 5 equals 1 with no remainder, therefore 5 % 5 is 0. And more generally, for an integer a, a % a will always be 0.

Consider the numbers 252 and 105; the GCD is 21. The difference of (252 - 105) is 147. The GCD of 147 and 105 is also 21. The difference of 147 - 105 is 63. And the GCD of 105 and 63 is also 21. And so on until we reach 0 for the smaller number.

gcd(252, 105) is 21
gcd(147, 105) is 21
gcd(105, 63)  is 21
gcd(63, 42)   is 21
gcd(42, 21)   is 21
gcd(21, 21)   is 21
gcd(21, 0)    is 21

Python examples

A simple implementation in Python would look as follows:

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

Even better, Python’s built-in math module includes gcd, which you can use as follows:

>>> from math import gcd
>>> gcd(252, 105)
21

Bonus

There is a faster and more elegant solution than our simple Python implementation. Consider the following which takes advantage of the yield statement and tuple assignment:

def gcd(x, y):
    while y != 0:
        (x, y) = (y, x % y)
    return x



Want to improve your Python? I have a list of recommended Python books.