GCD, LCM and the Extended Euclidean Algorithm

The greatest common divisor (GCD) is the largest integer dividing both a and b; the least common multiple (LCM) is the smallest positive integer both divide. Euclid's algorithm computes the GCD in O(log min(a, b)) steps, and its extended version also finds integers x, y with a*x + b*y = gcd(a, b), which answers every "can these two amounts combine into that one" question.

Intuition

Any number dividing both a and b also divides a - b, and therefore a mod b. So gcd(a, b) = gcd(b, a mod b), and the pair shrinks quickly: every two steps the larger number at least halves, giving O(log) steps. When b reaches 0, a is the answer.

The LCM follows from gcd(a, b) * lcm(a, b) = a * b.

Bezout's identity: the set of all values a*x + b*y (x, y any integers) is exactly the set of multiples of gcd(a, b). Consequences you will meet in interviews:

• Combining amounts a and b with additions and subtractions can produce exactly the multiples of their GCD (water jugs, reaching a value with two step sizes).
• A list of numbers can combine to 1 (with integer coefficients) iff the GCD of the list is 1.
• a*x + b*y = c has integer solutions iff gcd(a, b) divides c. If (x0, y0) is one solution, all solutions are x = x0 + k*(b/g), y = y0 - k*(a/g).

When to use it in interviews / OAs

• Simplifying fractions or ratios; canonical slopes as hash keys (points on a line).
• Periodicity: two cycles of lengths a and b align every lcm(a, b) steps; rotations of an array split into gcd(n, k) cycles.
• "Is it possible to reach / measure exactly c" with two quantities: check divisibility by the GCD.
• Repeating patterns in strings: the shortest common "divisor" string has length gcd(len(s), len(t)).

Template

def gcd(a: int, b: int) -> int:
    while b:  # gcd(a, b) = gcd(b, a mod b); inputs are non-negative
        a, b = b, a % b
    return a


def lcm(a: int, b: int) -> int:
    return a // gcd(a, b) * b  # divide first to keep the intermediate value small


def gcd_all(nums: list[int]) -> int:
    g = 0  # gcd(0, x) = x
    for x in nums:
        g = gcd(g, x)
        if g == 1:  # cannot get any smaller
            break
    return g


def ext_gcd(a: int, b: int) -> tuple[int, int, int]:
    # returns (g, x, y) with a*x + b*y == g == gcd(a, b)
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b:
        q = a // b
        a, b = b, a - q * b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

The extended version keeps the invariant that both current numbers are integer combinations of the original a and b; when the loop ends, the coefficients of the survivor are the Bezout coefficients. In Python, math.gcd and math.lcm (both accepting many arguments since 3.9) are the production choice.

Applying Bezout

Two jugs. With jugs of sizes x and y you can fill, empty and pour. Every reachable total is a multiple of gcd(x, y), every such total up to x + y is reachable, and nothing larger fits:

def can_measure(x: int, y: int, target: int) -> bool:
    if target > x + y:
        return False
    return target % gcd(x, y) == 0

Linear equations in integers. One solution comes from ext_gcd, scaled by c / g; shifting x by multiples of b / g gives all the others, so taking x mod (b / g) yields the smallest non-negative one.

def solve_linear(a: int, b: int, c: int) -> tuple[int, int] | None:
    # a, b > 0: find x, y with a*x + b*y == c and the smallest x >= 0
    g, x0, _ = ext_gcd(a, b)
    if c % g:
        return None  # no integer solution
    step = b // g  # x can move by multiples of b/g (y moves the other way by a/g)
    x = x0 * (c // g) % step
    y = (c - a * x) // b
    return x, y

The same ext_gcd gives modular inverses when the modulus is not prime: if gcd(a, m) = 1, the x in a*x + m*y = 1 is the inverse of a mod m.

Normalizing with the GCD

Dividing by the GCD gives each ratio or direction a unique representative, which makes it hashable:

def normalize_direction(dx: int, dy: int) -> tuple[int, int]:
    # canonical form of a non-zero direction, usable as a dict key for slopes
    g = gcd(abs(dx), abs(dy))
    dx, dy = dx // g, dy // g
    if dy < 0 or (dy == 0 and dx < 0):  # (2, -3) and (-2, 3) are the same line direction
        dx, dy = -dx, -dy
    return dx, dy


def gcd_of_strings(s: str, t: str) -> str:
    # a common divisor string exists only if s + t == t + s; its length is then the gcd
    if s + t != t + s:
        return ""
    return s[:gcd(len(s), len(t))]

Using a tuple of integers avoids the precision traps of floating-point slopes (and vertical lines need no special case).

Complexity

Euclid and extended Euclid take O(log min(a, b)) iterations. The GCD of a list costs O(n + log max) in total, because the running GCD only decreases. LCM of many numbers can grow very large: in fixed-width languages check for overflow before multiplying.

Common pitfalls

• Overflow in LCM: compute a / gcd(a, b) * b, not a * b / gcd(a, b). Even then the LCM of many numbers can exceed 64 bits.
• Negative inputs: % with negatives differs between languages. Take absolute values first when signs do not matter.
• gcd(0, 0) is 0 by convention, and gcd(0, x) = x; the list version relies on this as its starting value.
• Floating-point slopes: dy / dx loses precision and breaks on vertical lines; use the normalized integer pair.
• Forgetting divisibility: a*x + b*y = c only has solutions when gcd(a, b) divides c.

Interview variations

• Water and jug problem: Bezout's identity in disguise.
• Check if an array is "good" (some integer combination equals 1): GCD of all elements is 1.
• Max points on a line: hash normalized directions from each anchor point.
• X of a kind in a deck of cards: the GCD of all counts must be at least 2.
• GCD of strings, simplified fractions, fraction addition: reduce by the GCD.
• Nth magical number (multiples of a or b): binary search with n // a + n // b - n // lcm(a, b).
• Rotate an array in place: the rotation splits into gcd(n, k) independent cycles.