GCD, LCM & Linear Diophantine Equations

Intuition, Vocabulary and Foundations

The greatest common divisor answers a packing question: what is the largest unit that measures two integer quantities exactly? For lengths $84$ and $30$, the common positive divisors are $1,2,3,6$, so

$$ \gcd(84,30)=6. $$

A $6$-unit square is the largest square tile that can cover an $84$-by-$30$ rectangle without cutting. By convention, the gcd is nonnegative, signs do not matter, and $\gcd(a,0)=\lvert a\rvert$ while $\gcd(0,0)=0$.

The least common multiple answers the dual scheduling question: what is the smallest nonnegative quantity reached by whole multiples of both inputs? Cycles of $18$ and $24$ minutes first synchronize after $\operatorname{lcm}(18,24)=72$ minutes. If either argument is zero, the standard algorithmic convention sets the lcm to zero. For nonzero $a,b$,

$$ \gcd(a,b)\operatorname{lcm}(a,b)=\lvert ab\rvert. $$

Integers $a$ and $b$ are coprime when $\gcd(a,b)=1$. Coprime does not mean prime: $8$ and $15$ are both composite but share no positive divisor larger than $1$.

Bézout's identity turns the gcd into a constructive certificate. For integers $a,b$, not both zero, there are integers $x,y$ such that $ax+by=\gcd(a,b)$. For example, $84(-1)+30(3)=6$. Scaling such a certificate solves $ax+by=c$ exactly when $\gcd(a,b)\mid c$.

Step-by-Step Derivations and Algorithms

Euclid's algorithm follows from the division algorithm. Write $a=bq+r$. Any common divisor of $a$ and $b$ divides $r=a-bq$; any common divisor of $b$ and $r$ divides $a=bq+r$. Thus

$$ \gcd(a,b)=\gcd(b,r)=\gcd(b,a\bmod b). $$

Repeated replacement by $(b,a\bmod b)$ strictly decreases the nonnegative second component. For $84$ and $30$,

$$ 84=30\cdot2+24,\qquad 30=24\cdot1+6,\qquad 24=6\cdot4+0, $$

so the gcd is $6$.

Extended Euclid carries coefficients alongside each remainder. If $r_i=as_i+bt_i$, the update $r_{i+1}=r_{i-1}-qr_i$ is accompanied by

$$ s_{i+1}=s_{i-1}-qs_i,\qquad t_{i+1}=t_{i-1}-qt_i. $$

At termination the final nonzero remainder is $g=\gcd(a,b)$ and its coefficients satisfy $as+bt=g$. If $g\mid c$, multiplying by $c/g$ yields one solution $(x_0,y_0)$. Every solution is

$$ x=x_0+\frac bg t,\qquad y=y_0-\frac ag t,\qquad t\in\mathbb Z. $$

The step vector $(b/g,-a/g)$ preserves the equation because its total contribution is zero. Binary GCD instead uses parity, subtraction, and shifts, including $\gcd(2a,2b)=2\gcd(a,b)$ and $\gcd(2a,b)=\gcd(a,b)$ for odd $b$.

flowchart TD
    A["Division algorithm: a = bq + r"] --> B["Euclid: gcd(a,b) = gcd(b,r)"]
    B --> C["Final nonzero remainder g"]
    B --> D["Extended Euclid coefficient updates"]
    C --> E["LCM from reduced multiplication"]
    D --> F["Bézout certificate ax + by = g"]
    F --> G{"Does g divide c?"}
    G -->|No| H["No integer solution"]
    G -->|Yes| I["Scale one solution"]
    I --> J["Generate and bound the full family"]

Implementation, Complexity and Engineering

A robust gcd API returns a nonnegative value regardless of input signs and defines zero cases explicitly. Extended Euclid must restore coefficient signs after operating on magnitudes so its certificate still refers to the original inputs.

Compute lcm by dividing before multiplying:

$$ \operatorname{lcm}(a,b)=\left\lvert\frac{a}{\gcd(a,b)}b\right\rvert. $$

In fixed-width arithmetic, computing $\lvert ab\rvert/g$ first may overflow even when the final answer fits. Checked multiplication or a wider intermediate type remains necessary.

A Diophantine solver must distinguish no solution, a regular one-parameter family, and the degenerate equation $0x+0y=c$. Bounding a family requires exact floor and ceiling division: intersect the parameter interval from the $x$-bounds with that from the $y$-bounds.

from __future__ import annotations

from dataclasses import dataclass


@dataclass(frozen=True)
class DiophantineFamily:
    x0: int
    y0: int
    step_x: int
    step_y: int

    def at(self, t: int) -> tuple[int, int]:
        return self.x0 + self.step_x * t, self.y0 + self.step_y * t


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


def extended_gcd(a: int, b: int) -> tuple[int, int, int]:
    """Return g, x, y with g >= 0 and a*x + b*y = g."""
    old_r, r = abs(a), abs(b)
    old_x, x = 1, 0
    old_y, y = 0, 1
    while r:
        q = old_r // r
        old_r, r = r, old_r - q * r
        old_x, x = x, old_x - q * x
        old_y, y = y, old_y - q * y
    if a < 0:
        old_x = -old_x
    if b < 0:
        old_y = -old_y
    assert a * old_x + b * old_y == old_r
    return old_r, old_x, old_y


def lcm(a: int, b: int) -> int:
    if a == 0 or b == 0:
        return 0
    return abs((a // gcd(a, b)) * b)


def solve_diophantine(a: int, b: int, c: int) -> DiophantineFamily | None:
    if a == 0 and b == 0:
        if c == 0:
            raise ValueError("every integer pair solves 0*x + 0*y = 0")
        return None
    g, xg, yg = extended_gcd(a, b)
    if c % g != 0:
        return None
    scale = c // g
    family = DiophantineFamily(
        x0=xg * scale,
        y0=yg * scale,
        step_x=b // g,
        step_y=-(a // g),
    )
    assert a * family.x0 + b * family.y0 == c
    return family


def ceil_div(a: int, b: int) -> int:
    if b == 0:
        raise ZeroDivisionError("division by zero")
    return -((-a) // b)


def parameter_interval(
    base: int, step: int, low: int, high: int
) -> tuple[int, int] | None:
    """Find integer t values with low <= base + step*t <= high."""
    if low > high:
        raise ValueError("low must not exceed high")
    if step == 0:
        return None if not (low <= base <= high) else (-10**30, 10**30)
    if step > 0:
        return ceil_div(low - base, step), (high - base) // step
    return ceil_div(high - base, step), (low - base) // step


def solutions_in_box(
    a: int, b: int, c: int,
    x_low: int, x_high: int,
    y_low: int, y_high: int,
) -> list[tuple[int, int]]:
    family = solve_diophantine(a, b, c)
    if family is None:
        return []
    xr = parameter_interval(family.x0, family.step_x, x_low, x_high)
    yr = parameter_interval(family.y0, family.step_y, y_low, y_high)
    if xr is None or yr is None:
        return []
    low, high = max(xr[0], yr[0]), min(xr[1], yr[1])
    return [] if low > high else [family.at(t) for t in range(low, high + 1)]


def run_tests() -> None:
    assert gcd(84, 30) == 6
    assert gcd(-84, 30) == 6
    assert gcd(0, 0) == 0
    g, x, y = extended_gcd(84, 30)
    assert (g, 84 * x + 30 * y) == (6, 6)
    assert lcm(18, 24) == 72
    assert lcm(0, 24) == 0
    assert gcd(18, 24) * lcm(18, 24) == abs(18 * 24)
    assert solve_diophantine(6, 9, 50) is None

    family = solve_diophantine(6, 9, 48)
    assert family is not None
    for t in range(-5, 6):
        px, py = family.at(t)
        assert 6 * px + 9 * py == 48

    bounded = solutions_in_box(6, 9, 48, 0, 10, 0, 10)
    assert bounded == [(2, 4), (5, 2), (8, 0)]

    shipping = solutions_in_box(84, 126, 2100, 0, 100, 0, 100)
    assert len(shipping) == 9
    assert min(shipping, key=lambda pair: sum(pair)) == (1, 16)


if __name__ == "__main__":
    run_tests()
    print("all gcd and Diophantine tests passed")

Applications, Case Studies and Exercises

GCD and lcm reveal shared structure before expensive search begins. They identify the largest reusable unit, the first synchronization time, and the lattice of totals reachable by integer combinations. Extended Euclid turns existence proofs into certificates and parameterized solutions.