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.