Euclidean Algorithm Explained: GCD, LCM and Extended Euclid

The Euclidean algorithm is more than two thousand years old and still the way computers find the greatest common divisor. It is three lines of code, and the interview questions around it are rarely about writing those lines. They ask why it is correct, how many steps it takes, and what else it gives you for free: the least common multiple, reduced fractions, and, with one extension, the modular inverses that hashing and cryptography depend on.

The problem it solves

The greatest common divisor of two integers is the largest integer that divides both. gcd(48, 18) is 6. The obvious method tries every candidate from the smaller number downwards, which takes up to min(a, b) divisions: fine for 48 and 18, useless for numbers with twenty digits. Factorising both numbers is worse, because nobody knows a fast way to factorise large numbers.

Euclid's algorithm needs neither. It finds the gcd in a number of steps proportional to the number of digits, not the size of the numbers.

The intuition

Think of the gcd as the longest ruler that measures both lengths exactly. Lay the shorter length b along the longer length a as many times as it fits. Whatever sticks out, the remainder a % b, must also be measured exactly by any ruler that measures both a and b, because it is a minus a whole number of copies of b. The argument works backwards too: any ruler that measures b and the remainder also measures a. So the two pairs have exactly the same common divisors, and therefore the same greatest one:

gcd(a, b) = gcd(b, a % b)

Each step replaces the pair with a strictly smaller one. When the remainder reaches zero, the last divisor measured the previous number exactly, and it is the answer. gcd(a, 0) is a by definition, since every integer divides zero.

Why is it fast? After two steps the first number has at least halved. If b is at most half of a, the remainder is below b, so below half. If b is more than half, the remainder is a - b, again less than half. Halving every two steps means O(log min(a, b)) steps. The slowest inputs are consecutive Fibonacci numbers, where every quotient is 1 and the pair shrinks as slowly as possible; this worst case is known as Lamé's theorem. The Big-O cheat sheet lists the same bound.

Two useful corollaries fall out. lcm(a, b) = a / gcd(a, b) × b, and a fraction is reduced by dividing both parts by their gcd.

Watch it run

The animation opens with the definition: the greatest common divisor is the longest ruler that measures both lengths exactly. It lays the 18 along the 48: two whole copies fit and 12 sticks out. Any ruler that measures 48 and 18 must measure that leftover too, so gcd(48, 18) = gcd(18, 12). It makes the same move on the smaller pair: one 12 fits inside 18 and 6 is left. Then again with 12 and 6, and this time the shorter ruler fits exactly twice. A remainder of zero is the stop sign, and the last divisor, 6, is the answer. The closing frame shows six measuring both lengths with nothing over, after only three divisions.

The code

The lesson's loop, with abs so negative inputs return the non-negative gcd, and a trace that prints the same three divisions as the animation:

def gcd(a, b):
    a, b = abs(a), abs(b)                  # the gcd is defined as non-negative
    while b:
        a, b = b, a % b                    # the leftover becomes the next divisor
    return a

def gcd_trace(a, b):
    steps = []
    while b:
        steps.append(f"{a} = {a // b}*{b} + {a % b}")
        a, b = b, a % b
    return steps

print(gcd_trace(48, 18))   # ['48 = 2*18 + 12', '18 = 1*12 + 6', '12 = 2*6 + 0']
print(gcd(48, 18), gcd(18, 48), gcd(13, 7))   # 6 6 1
print(gcd(0, 9), gcd(0, 0), gcd(-48, 18))     # 9 0 6

The least common multiple and a reduced aspect ratio. Dividing before multiplying keeps the intermediate value small, which matters in languages with fixed-width integers:

def lcm(a, b):
    return a // gcd(a, b) * b if a and b else 0    # divide first: smaller intermediate

w, h = 1920, 1080
g = gcd(w, h)
print(g, f"{w // g}:{h // g}", lcm(48, 18))        # 120 16:9 144

Why the modulo matters. The subtraction form of Euclid is correct but can take a step per unit of the quotient; division collapses those steps into one. The slowest pair found below 1,000 is two consecutive Fibonacci numbers, and even a seven-digit Fibonacci pair needs only 30 divisions:

def gcd_by_subtraction(a, b):
    steps = 0
    while a and b:
        if a > b:
            a -= b
        else:
            b -= a
        steps += 1
    return a or b, steps

def divisions(a, b):
    steps = 0
    while b:
        a, b = b, a % b
        steps += 1
    return steps

print(gcd_by_subtraction(1000000, 3), divisions(1000000, 3))   # (1, 333336) 2

fib = [1, 1]
while len(fib) < 32:
    fib.append(fib[-1] + fib[-2])
worst = max(((a, b) for a in range(1, 1000) for b in range(1, a + 1)), key=lambda p: divisions(*p))
print(worst, divisions(*worst))                      # (987, 610) 14
print(divisions(fib[31], fib[30]), fib[31])          # 30 2178309

Extended Euclid also returns x and y with a·x + b·y = gcd(a, b). When the gcd is 1, x is the inverse of a modulo b: here 15, because 7 × 15 = 105, which is 1 more than 4 × 26:

def ext_gcd(a, b):
    """Return (g, x, y) with a*x + b*y == g."""
    if b == 0:
        return a, 1, 0
    g, x, y = ext_gcd(b, a % b)
    return g, y, x - (a // b) * y

print(ext_gcd(48, 18))                  # (6, -1, 3)
g, x, _ = ext_gcd(7, 26)
print(x % 26, 7 * (x % 26) % 26)        # 15 1

Checked against a brute-force search for the largest common divisor and against math.gcd on 3,000 seeded random pairs, including zeros and negatives, with the LCM, the subtraction form and extended Euclid checked on the positive pairs:

import math
import random

random.seed(23)
ok = True
for _ in range(3000):
    a, b = random.randint(-300, 300), random.randint(-300, 300)
    brute = max((d for d in range(1, max(abs(a), abs(b)) + 1) if a % d == 0 and b % d == 0), default=0)
    ok &= gcd(a, b) == brute == math.gcd(a, b)
    if a > 0 and b > 0:
        ok &= gcd_by_subtraction(a, b)[0] == brute
        ok &= lcm(a, b) == min(m for m in range(max(a, b), a * b + 1) if m % a == 0 and m % b == 0)
        g, x, y = ext_gcd(a, b)
        ok &= g == brute and a * x + b * y == g
print(ok)                               # True

The complexity

• Time: O(log min(a, b)) divisions. With arbitrary-precision integers each division also costs time proportional to the digits.
• Space: O(1) for the loop; the recursive and extended versions use O(log min(a, b)) stack frames.
• LCM: one gcd plus one division and one multiplication.

Where it goes wrong

• Returning a for negative inputs. Python's % follows the sign of the divisor, so without abs a negative second argument can produce a negative result.
• Computing a * b // gcd(a, b). Correct in Python, but the product overflows first in languages with 64-bit integers. Divide first.
• Forgetting gcd(0, 0). Mathematically it is 0 by convention; code that divides by the gcd must handle it.
• Using subtraction instead of modulo. It is correct but can be linear in the size of the numbers.
• Expecting an inverse when the gcd is not 1. A modular inverse exists only for coprime numbers.

When it shows up in interviews

It appears inside other problems more often than on its own: simplifying fractions, the greatest common divisor of strings, water-jug puzzles, rotating an array by k with cycles of length n / gcd(n, k), and checking whether a set of step sizes can reach a target. Modular inverses from extended Euclid show up next to fast exponentiation whenever an answer is taken modulo a prime, and the sieve of Eratosthenes is the other number theory tool worth having ready.

How to say it in an interview

"Any common divisor of a and b also divides a mod b, and the reverse holds too, so gcd(a, b) = gcd(b, a mod b). I repeat that until the second number is zero, and the first number is the answer. The first number at least halves every two steps, so it takes O(log min(a, b)) divisions, with consecutive Fibonacci numbers as the worst case. I take absolute values for negative inputs, compute the LCM as a / gcd × b to avoid overflow, and if I need a modular inverse I use the extended version, which also returns the coefficients."