Euclidean algorithm: Greatest common divisor

In short: A very old, fast method for computing the greatest common divisor (gcd) of two numbers by repeated division with remainder.

In more detail: The gcd of 48 and 18 is 6, the largest number that divides both. Instead of listing all divisors, Euclid (around 300 BC) uses the observation: gcd(a, b) = gcd(b, a mod b). You replace the pair with (b, remainder) and repeat until the remainder is 0. The last non-zero number is the gcd.

In Depth

Example

gcd(48, 18):

48 mod 18 = 12   ->  gcd(18, 12)
18 mod 12 = 6    ->  gcd(12, 6)
12 mod 6  = 0    ->  gcd = 6

Code

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a
 
print(gcd(48, 18))  # 6

Recursively: gcd(a, b) = a if b == 0 else gcd(b, a % b). The least common multiple follows from it: lcm(a, b) = a / gcd(a, b) * b.

How fast?

The number of steps grows only with the length of the numbers (logarithmically), not with their value. The worst case is consecutive Fibonacci numbers. This makes the algorithm practical even for very large numbers, for example in cryptography.

Extension and use

The extended Euclidean algorithm additionally yields numbers x and y with a·x + b·y = gcd(a, b). With it you compute the modular inverse, needed for RSA among other things. In everyday life you use it to reduce fractions: divide numerator and denominator by their gcd.

See also: Recursion, Big O notation, Algorithms