GCD / LCM (Euclidean Algorithm)

GCD, LCM, and the Euclidean Algorithm

The greatest common divisor (GCD) of two integers is the largest positive integer that divides both without a remainder. It shows up constantly in competitive programming: simplifying fractions, checking whether two lengths can tile a rectangle, finding the period hidden inside a sequence. The Euclidean algorithm computes it in $O(\log(\min(a, b)))$, fast enough that even calling it millions of times inside a loop is usually fine.

Why the Euclidean Algorithm Works

The algorithm rests on a single identity:

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

Proof sketch: any divisor of both a and b must also divide a % b = a - floor(a/b)*b, so the set of common divisors is unchanged when you replace a with a % b. Repeating this replacement shrinks the numbers rapidly, since the remainder is always strictly less than the divisor, until the smaller value reaches zero, at which point the other value is the GCD.

Walked Example: gcd(48, 18)

Starting with 48 and 18:

• gcd(48, 18): 48 % 18 = 12 → gcd(18, 12)
• gcd(18, 12): 18 % 12 = 6 → gcd(12, 6)
• gcd(12, 6): 12 % 6 = 0 → gcd(6, 0)
• gcd(6, 0): b is zero, return 6.

So gcd(48, 18) = 6. Three steps to reduce two two-digit numbers. For 64-bit integers the algorithm never needs more than about 93 steps.

Iterative Implementation

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

Python 3.5+ ships math.gcd, but knowing the implementation matters when you need to adapt it (e.g., extended GCD, or GCD over negative numbers where you want abs guards).

Least Common Multiple

The LCM of two numbers is the smallest positive integer divisible by both. Trying to compute it directly by multiplying and dividing is fine for small values but overflows with large integers if you're not careful. The safe formula divides first:

lcm(a, b) = a // gcd(a, b) * b

Dividing a by gcd(a, b) before multiplying by b keeps intermediate values smaller.

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

GCD and LCM of Arrays

Both operations are associative and commutative, so you can reduce an entire array pairwise. Python's functools.reduce handles this cleanly. The identity element for GCD is 0 (since gcd(0, x) = x for any positive x), which means you can safely fold over an empty prefix.

from math import gcd
from functools import reduce

def array_gcd(nums: list[int]) -> int:
    return reduce(gcd, nums)

def array_lcm(nums: list[int]) -> int:
    return reduce(lcm, nums)

A useful trick: if array_gcd(nums) == 1, the numbers are coprime as a group. In problems about reachable sums or coin denominators, coprimality is often the condition that makes every sufficiently large integer reachable.

Extended Euclidean Algorithm and Bezout's Identity

The standard Euclidean algorithm tells you the GCD. The extended version also tells you the integer coefficients x and y satisfying:

a*x + b*y = gcd(a, b)

This is Bezout's identity. It's the foundation of modular inverse computation: if gcd(a, m) = 1, then the x returned by ext_gcd(a, m) is a's inverse modulo m.

def ext_gcd(a: int, b: int) -> tuple[int, int, int]:
    """Returns (g, x, y) such that a*x + b*y = g = gcd(a, b)."""
    if b == 0:
        return a, 1, 0
    g, x, y = ext_gcd(b, a % b)
    # Back-substitute: new x = old y, new y = old x - (a//b)*old y
    return g, y, x - (a // b) * y

Walked Example: ext_gcd(48, 18)

Tracing the recursion:

• ext_gcd(48, 18) calls ext_gcd(18, 12)
• ext_gcd(18, 12) calls ext_gcd(12, 6)
• ext_gcd(12, 6) calls ext_gcd(6, 0) → returns (6, 1, 0)
• Back-sub in ext_gcd(12, 6): (6, 0, 1 - 2*0) = (6, 0, 1)
• Back-sub in ext_gcd(18, 12): (6, 1, 0 - 1*1) = (6, 1, -1)
• Back-sub in ext_gcd(48, 18): (6, -1, 1 - 2*(-1)) = (6, -1, 3)

Check: 48*(-1) + 18*3 = -48 + 54 = 6. Correct.

Modular Inverse via Extended GCD

When you need to divide inside a modular arithmetic expression, say, to compute (a / b) % p where p is prime, you need the modular inverse of b. The extended GCD gives it directly when gcd(b, p) = 1 (always true if p is prime and b is not a multiple of p):

def mod_inverse(b: int, p: int) -> int:
    g, x, _ = ext_gcd(b % p, p)
    if g != 1:
        raise ValueError("Inverse does not exist")
    return x % p

Python 3.8+ also provides pow(b, -1, p) for the same result, but the extended GCD is more portable and instructive.

LeetCode Variants

• LeetCode 1979. Find Greatest Common Divisor of Array: a direct application: locate the min and max, then return gcd(min, max). The full array reduce also works.
• LeetCode 914. X of a Kind in a Deck of Cards: the deck can be split into groups of size $\geq 2$ iff the GCD of all card-value frequencies is $\geq 2$.
• LeetCode 1071. Greatest Common Divisor of Strings: the longest string that divides both s and t is the prefix of length gcd(len(s), len(t)), provided s + t == t + s.
• LeetCode 1390. Four Divisors and LeetCode 2447. Number of Subarrays With GCD Equal to K: both lean on incremental GCD updates.
• LeetCode 365. Water and Jug Problem: you can measure z liters with jugs of size x and y iff z is a multiple of gcd(x, y) and z \leq x + y, a direct consequence of Bezout's identity.
• LeetCode 858. Mirror Reflection: reduces p and q by their GCD before classifying which receptor is hit.

Other Common Uses

• Simplifying fractions: divide numerator and denominator by their GCD.
• Rope cutting: given ropes of various lengths, the longest piece that cuts all of them evenly is the GCD of all lengths.
• Coprimality and reachability: if gcd of a set of denominations is d, every sufficiently large multiple of d is representable (Chicken McNugget / Frobenius theorem).
• Chinese Remainder Theorem: combining congruences requires extended GCD to find the combined modulus.

Complexity

Each GCD call runs in $O(\log(\min(a, b)))$ time and, for the iterative version, $O(1)$ space. The recursive extended GCD uses $O(\log(\min(a, b)))$ stack frames. Reducing an array of n numbers via pairwise GCD costs $O(n \log V)$ where $V$ is the maximum value.

Recognizing this pattern

You're probably looking at GCD / LCM / Euclidean algorithm when:

• The problem talks about divisibility, common factors, or common multiples of integers.
• You need to shrink a fraction to lowest terms, or check whether two integers are coprime.
• The setup is a water-jug puzzle, a rope-cutting puzzle, or any "can I measure exactly z using steps of x and y" question.
• You need a modular inverse, Bezout coefficients, or the answer hinges on gcd(a, m) = 1.

Common templates:

• Pairwise GCD reduction: collapse an array to a single GCD by folding. Example: Find Greatest Common Divisor of Array.
• Bezout / linear combination: z is reachable iff gcd(x, y) divides z. Example: Water and Jug Problem.
• GCD of lengths: the longest common divisor string has length gcd(len(s), len(t)). Example: Greatest Common Divisor of Strings.
• Extended Euclidean / modular inverse: solve ax + by = gcd(a, b) to invert under a modulus. Example: Number of Subarrays With GCD Equal to K.