GCD and LCM — Euclidean Algorithm

The Euclidean algorithm is 2300 years old, appears in Euclid's Elements (Book VII, Proposition 2), and is still one of the fastest algorithms relative to input size that exists. For 64-bit numbers, it terminates in at most 93 steps. The RSA cryptographic system — which secures most HTTPS traffic — depends on extended Euclidean to compute private keys. Every time your browser establishes a TLS connection, a variant of this algorithm runs.

The extended Euclidean algorithm (Bézout's identity: ax + by = GCD(a,b)) is the computational backbone of modular inverses. Modular inverses are the backbone of modular arithmetic. Modular arithmetic is the backbone of RSA, Diffie-Hellman, elliptic curve cryptography, and the Chinese Remainder Theorem. The entire edifice of public-key cryptography rests on an algorithm Euclid described in 300 BC.

Euclidean Algorithm for GCD

Based on the identity: GCD(a, b) = GCD(b, a mod b). Repeat until b = 0 — then GCD = a.

def gcd(a: int, b: int) -> int:
    while b:
        a, b = b, a % b
    return a

def gcd_recursive(a: int, b: int) -> int:
    return a if b == 0 else gcd_recursive(b, a % b)

def lcm(a: int, b: int) -> int:
    return a * b // gcd(a, b)  # avoid overflow: a // gcd * b

print(gcd(252, 105))    # 21
print(gcd(48, 18))      # 6
print(lcm(12, 18))      # 36
print(lcm(4, 6))        # 12

# Python 3.9+ built-in
import math
print(math.gcd(252, 105))  # 21
print(math.lcm(12, 18))    # 36

Why the Euclidean Algorithm is Fast

Each step reduces the larger number by at least half every two steps. More precisely, after two iterations: a mod b < a/2. This gives O(log min(a,b)) steps — for 64-bit numbers, at most ~93 iterations. The Fibonacci numbers are the worst case — GCD(F(n+1), F(n)) requires exactly n steps.

Extended Euclidean Algorithm

Finds integers x, y such that ax + by = GCD(a,b) (Bézout's identity). Essential for computing modular inverses.

def extended_gcd(a: int, b: int) -> tuple[int, int, int]:
    """Returns (gcd, x, y) such that a*x + b*y = gcd."""
    if b == 0:
        return a, 1, 0
    g, x1, y1 = extended_gcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return g, x, y

g, x, y = extended_gcd(35, 15)
print(f'GCD={g}, x={x}, y={y}')         # GCD=5, x=1, y=-2
print(f'Verify: 35*{x} + 15*{y} = {35*x + 15*y}')  # = 5

# Modular inverse: find x such that a*x ≡ 1 (mod m)
def mod_inverse(a: int, m: int) -> int:
    g, x, _ = extended_gcd(a % m, m)
    if g != 1:
        raise ValueError(f'{a} has no inverse mod {m}')
    return x % m

print(mod_inverse(3, 7))   # 5 (since 3*5=15≡1 mod 7)
print(mod_inverse(17, 26)) # 3 (since 17*3=51≡25... wait)
print(3 * mod_inverse(3, 7) % 7)  # 1 ✓

LCM for Multiple Numbers

LCM of multiple numbers via pairwise LCM. Used for scheduling (when do cycles align?) and fraction arithmetic.

from math import gcd
from functools import reduce

def lcm_multiple(*nums) -> int:
    return reduce(lambda a, b: a * b // gcd(a, b), nums)

print(lcm_multiple(4, 6, 10))    # 60
print(lcm_multiple(3, 4, 5, 6))  # 60

# When do three periodic events align?
# Event A: every 4 days, B: every 6 days, C: every 10 days
print(f'All align on day: {lcm_multiple(4, 6, 10)}')  # 60

Applications

GCD and extended GCD appear throughout computer science:

RSA cryptography: Extended GCD computes the private key d = e⁻¹ mod φ(n). Fraction simplification: a/b in lowest terms = (a/gcd)/(b/gcd). Chinese Remainder Theorem: Extended GCD computes the modular inverses needed. Scheduling: LCM gives when periodic tasks next align. Competitive programming: GCD appears in almost every number theory problem.

Frequently Asked Questions