Eric Campbell 7 min read Engineering

GCD and LCM: Euclidean Algorithm

The Greatest Common Divisor (GCD) of two integers is the largest positive integer that divides both numbers without leaving a remainder. The Least Common Multiple (LCM) is the smallest positive...

Key Insights

  • The Euclidean algorithm computes GCD in O(log(min(a, b))) time, making it exponentially faster than brute-force approaches that check every possible divisor.
  • The Extended Euclidean Algorithm finds coefficients x and y such that ax + by = GCD(a, b), which is essential for computing modular inverses in cryptographic applications.
  • Computing LCM through GCD using the formula LCM(a, b) = |a × b| / GCD(a, b) requires careful ordering of operations to prevent integer overflow.

Introduction to GCD and LCM

The Greatest Common Divisor (GCD) of two integers is the largest positive integer that divides both numbers without leaving a remainder. The Least Common Multiple (LCM) is the smallest positive integer that is divisible by both numbers. These concepts appear deceptively simple, but they underpin critical systems across computing.

Cryptographic algorithms like RSA rely on GCD computations for key generation and modular arithmetic. Fraction simplification in computer algebra systems requires finding GCDs to reduce ratios to lowest terms. Scheduling problems—determining when two periodic events coincide—depend on LCM calculations. Even something as mundane as resizing images while maintaining aspect ratios involves GCD operations.

Understanding efficient algorithms for these operations isn’t academic trivia. It’s foundational knowledge that separates engineers who write performant code from those who don’t.

The Naive Approach

The most intuitive way to find the GCD is to check every integer from 1 up to the smaller of the two numbers and track the largest one that divides both evenly.

def gcd_naive(a: int, b: int) -> int:
    """Brute-force GCD computation."""
    a, b = abs(a), abs(b)
    if a == 0:
        return b
    if b == 0:
        return a
    
    result = 1
    smaller = min(a, b)
    
    for i in range(1, smaller + 1):
        if a % i == 0 and b % i == 0:
            result = i
    
    return result

This works, but the time complexity is O(min(a, b)). For small numbers, this is fine. For numbers in the millions or billions—common in real applications—this approach becomes unusable. Computing GCD(1000000007, 998244353) would require checking roughly a billion candidates.

You can optimize slightly by iterating downward and returning the first common divisor found, but the worst-case complexity remains linear. We need a fundamentally different approach.

The Euclidean Algorithm Explained

The Euclidean algorithm, documented around 300 BCE, remains one of the most elegant algorithms in computer science. It relies on a simple observation: the GCD of two numbers also divides their difference.

More precisely: GCD(a, b) = GCD(b, a mod b)

Here’s why this works. If d divides both a and b, then d also divides (a - kb) for any integer k. Since a mod b = a - (a // b) × b, any common divisor of a and b must also divide a mod b. The converse holds as well, so GCD(a, b) = GCD(b, a mod b).

Let’s trace through GCD(48, 18):

  1. GCD(48, 18) → 48 mod 18 = 12 → GCD(18, 12)
  2. GCD(18, 12) → 18 mod 12 = 6 → GCD(12, 6)
  3. GCD(12, 6) → 12 mod 6 = 0 → GCD(6, 0)
  4. When we reach GCD(n, 0), the answer is n. So GCD(48, 18) = 6.
def gcd_iterative(a: int, b: int) -> int:
    """Euclidean algorithm - iterative implementation."""
    a, b = abs(a), abs(b)
    
    while b != 0:
        a, b = b, a % b
    
    return a

Three lines of actual logic. That’s the entire algorithm. Each iteration reduces the larger number by at least half (you can prove this), giving us O(log(min(a, b))) time complexity—a dramatic improvement over the naive approach.

Recursive Implementation

The mathematical definition of the Euclidean algorithm is inherently recursive, and the code can reflect that directly.

def gcd_recursive(a: int, b: int) -> int:
    """Euclidean algorithm - recursive implementation."""
    a, b = abs(a), abs(b)
    
    if b == 0:
        return a
    return gcd_recursive(b, a % b)

This is arguably more readable—it mirrors the mathematical definition exactly. However, there’s a tradeoff. Each recursive call adds a frame to the call stack. For extremely large numbers requiring many iterations, you could hit Python’s recursion limit (default 1000) or cause stack overflow in languages without tail-call optimization.

In practice, this rarely matters. The logarithmic complexity means even GCD(10^18, 10^18) requires at most about 87 iterations. But for production code processing untrusted input, the iterative version is safer.

# Comparison: both produce identical results
print(gcd_iterative(1234567890, 987654321))  # 9
print(gcd_recursive(1234567890, 987654321))  # 9

Extended Euclidean Algorithm

The Extended Euclidean Algorithm goes further: it finds integers x and y such that ax + by = GCD(a, b). This equation is known as Bézout’s identity, and it always has integer solutions.

Why does this matter? Computing modular multiplicative inverses. If you need to find x such that ax ≡ 1 (mod m), and GCD(a, m) = 1, then the Extended Euclidean Algorithm gives you the answer directly. This operation is fundamental to RSA encryption, elliptic curve cryptography, and countless other applications.

def extended_gcd(a: int, b: int) -> tuple[int, int, int]:
    """
    Extended Euclidean Algorithm.
    
    Returns (gcd, x, y) such that a*x + b*y = gcd.
    """
    if b == 0:
        return a, 1, 0
    
    gcd, x1, y1 = extended_gcd(b, a % b)
    
    # Back-substitute to find coefficients for current level
    x = y1
    y = x1 - (a // b) * y1
    
    return gcd, x, y


def mod_inverse(a: int, m: int) -> int:
    """
    Compute modular multiplicative inverse of a modulo m.
    
    Returns x such that (a * x) % m == 1.
    Raises ValueError if inverse doesn't exist.
    """
    gcd, x, _ = extended_gcd(a, m)
    
    if gcd != 1:
        raise ValueError(f"Modular inverse doesn't exist: GCD({a}, {m}) = {gcd}")
    
    return x % m  # Ensure positive result

Let’s verify with an example:

gcd, x, y = extended_gcd(35, 15)
print(f"GCD: {gcd}, x: {x}, y: {y}")  # GCD: 5, x: 1, y: -2
print(f"Verification: 35*{x} + 15*{y} = {35*x + 15*y}")  # 35*1 + 15*-2 = 5

# Modular inverse example
inv = mod_inverse(3, 11)
print(f"Inverse of 3 mod 11: {inv}")  # 4
print(f"Verification: 3 * {inv} mod 11 = {(3 * inv) % 11}")  # 1

Computing LCM Using GCD

The relationship between GCD and LCM is elegant: LCM(a, b) × GCD(a, b) = |a × b|

Rearranging: LCM(a, b) = |a × b| / GCD(a, b)

The naive implementation has a subtle bug that causes integer overflow for large inputs:

def lcm_naive(a: int, b: int) -> int:
    """LCM computation - potentially problematic for large numbers."""
    return abs(a * b) // gcd_iterative(a, b)

If a and b are both near the maximum integer size, their product overflows before the division occurs. The fix is to divide first:

def lcm(a: int, b: int) -> int:
    """LCM computation - overflow-safe version."""
    if a == 0 or b == 0:
        return 0
    
    # Divide before multiplying to prevent overflow
    return abs(a // gcd_iterative(a, b) * b)

In Python, integers have arbitrary precision, so overflow isn’t a concern. But this pattern matters enormously in C, C++, Java, Rust, and other languages with fixed-width integers. Always divide first.

# LCM examples
print(lcm(12, 18))  # 36
print(lcm(7, 5))    # 35 (coprime numbers: LCM = product)
print(lcm(0, 5))    # 0 (edge case)

Performance Analysis and Edge Cases

The Euclidean algorithm’s time complexity deserves closer examination. The worst case occurs with consecutive Fibonacci numbers, where each iteration reduces the numbers by the minimum possible amount. Even then, the algorithm completes in O(log(min(a, b))) steps.

Here’s a production-ready implementation with proper edge case handling:

class NumberTheory:
    """Utility class for GCD and LCM operations with full edge case handling."""
    
    @staticmethod
    def gcd(a: int, b: int) -> int:
        """
        Compute GCD of two integers.
        
        Handles: negative numbers, zeros, arbitrary precision integers.
        Time complexity: O(log(min(|a|, |b|)))
        """
        a, b = abs(a), abs(b)
        while b:
            a, b = b, a % b
        return a
    
    @staticmethod
    def gcd_multiple(*args: int) -> int:
        """Compute GCD of multiple integers."""
        from functools import reduce
        if not args:
            raise ValueError("At least one argument required")
        return reduce(NumberTheory.gcd, args)
    
    @staticmethod
    def lcm(a: int, b: int) -> int:
        """
        Compute LCM of two integers.
        
        Uses overflow-safe computation order.
        """
        if a == 0 or b == 0:
            return 0
        return abs(a // NumberTheory.gcd(a, b) * b)
    
    @staticmethod
    def lcm_multiple(*args: int) -> int:
        """Compute LCM of multiple integers."""
        from functools import reduce
        if not args:
            raise ValueError("At least one argument required")
        return reduce(NumberTheory.lcm, args)
    
    @staticmethod
    def extended_gcd(a: int, b: int) -> tuple[int, int, int]:
        """Returns (gcd, x, y) where a*x + b*y = gcd."""
        if b == 0:
            return abs(a), 1 if a >= 0 else -1, 0
        
        gcd, x1, y1 = NumberTheory.extended_gcd(b, a % b)
        return gcd, y1, x1 - (a // b) * y1


# Test suite
def run_tests():
    nt = NumberTheory
    
    # Basic GCD tests
    assert nt.gcd(48, 18) == 6
    assert nt.gcd(0, 5) == 5
    assert nt.gcd(5, 0) == 5
    assert nt.gcd(-12, 8) == 4
    assert nt.gcd(17, 23) == 1  # Coprime
    
    # Multiple GCD
    assert nt.gcd_multiple(12, 18, 24) == 6
    
    # LCM tests
    assert nt.lcm(4, 6) == 12
    assert nt.lcm(0, 5) == 0
    assert nt.lcm(7, 11) == 77
    
    # Extended GCD verification
    for a, b in [(35, 15), (120, 23), (17, 31)]:
        gcd, x, y = nt.extended_gcd(a, b)
        assert a * x + b * y == gcd
    
    print("All tests passed!")

run_tests()

The Euclidean algorithm is one of those rare algorithms that’s both theoretically elegant and practically optimal. It’s been in use for over two millennia because nothing better exists for the general case. Learn it, internalize it, and use it whenever GCD or LCM computations arise in your code.

Liked this? There's more.

Every week: one practical technique, explained simply, with code you can use immediately.