GCD & LCMGreatest common divisor

01Why it exists

Reach for it when you see:Greatest common divisor, least common multiple, reducing a fraction, a common denominator, ratios, when two periods coincide again, divisibility, whether ax + by = c has integer solutions, an inverse when the modulus is not prime, the common divisor of a whole array.

02The core idea

The Euclidean algorithm rests on a single identity: gcd(a, b) = gcd(b, a mod b). The reason is that a mod b = a − q·b. Anything that divides both a and b must also divide a − q·b; conversely, anything that divides both b and the remainder r must divide a = q·b + r. The two pairs have exactly the same set of common divisors, so of course they have the same largest one. Every round shrinks the numbers until the remainder is 0, and gcd(g, 0) = g. At no point does the algorithm need to know the prime factors of a or b, which is why it is so much faster than factoring both numbers and intersecting the results.

Why it is fast: look at two consecutive steps, (a, b) → (b, r) → (r, r′). If b ≤ a/2, then r < b ≤ a/2. If b > a/2, the quotient can only be 1, so r = a − b < a/2. Either way the first number at least halves every two steps, which puts the number of divisions at O(log min(a, b)). The worst case is a pair of consecutive Fibonacci numbers, where every quotient is 1 and the shrinking is as slow as it gets — gcd(89, 55) takes 9 divisions. The loop version uses two variables, so O(1) space; the recursive version needs an O(log) call stack. The least common multiple comes from gcd(a, b) × lcm(a, b) = a × b, written as a / gcd × b. For several numbers, fold pairwise for O(n log M) overall, where M is the largest value; and once the running gcd reaches 1 you can stop early.

Extended Euclid finds, alongside the gcd, integers x and y with ax + by = gcd(a, b). Such a pair always exists — this is Bézout's identity. The recursive derivation: suppose you already have b·x′ + (a mod b)·y′ = g; substitute a mod b = a − ⌊a/b⌋·b and regroup to get x = y′ and y = x′ − ⌊a/b⌋·y′. Two immediate consequences: ax + by = c has integer solutions if and only if g divides c; and when gcd(a, m) = 1, reducing ax + my = 1 modulo m gives ax ≡ 1, so x is the modular inverse of a. The Modular Arithmetic lesson gets inverses from Fermat's little theorem and fast exponentiation, but that requires a prime modulus — extended Euclid only requires the two numbers to be coprime.

Common traps: using the subtraction form gcd(a − b, b) instead of the remainder, which makes gcd(10⁹, 1) take a billion subtractions; forgetting that C++'s % follows the sign of the dividend, so negatives need absolute values first (C++17's std::gcd already handles this); writing lcm as a * b / gcd, which overflows before the division ever happens and divides by zero when a or b is 0; and using the x from extended Euclid as an inverse without first applying (x % m + m) % m, since it is often negative. When fractions show up in a problem, store them as a reduced (numerator, denominator) pair with the sign always on the numerator: no floating-point error, and the pair works directly as a hash table key.

03The algorithm

1. 1Take absolute values first. By convention gcd(a, 0) = a, so gcd(0, 0) = 0.
2. 2while b != 0: a, b = b, a % b. When the loop ends, a is the greatest common divisor. There is no need to swap when a < b — the first round does it for you.
3. 3Least common multiple: return 0 if either number is 0, otherwise return a // gcd(a, b) * b, dividing before multiplying. For more than two numbers, fold gcd or lcm left to right.
4. 4Extended version: when b == 0, return (a, 1, 0); otherwise recurse to get (g, x′, y′) and return (g, y′, x′ − (a // b)·y′). The iterative version keeps r = a·s + b·t true on every row, advancing r, s and t by the same "row before last − q × last row" rule.
5. 5Applications: to solve ax + by = c, first check c % g == 0; when it is solvable, multiply x and y by c / g. For the inverse of a modulo m, confirm g == 1 and take x % m (pulled back into 0 to m − 1).

04Interactive demo

Using 252 and 105, in two stages. The first is the Euclidean algorithm: on the left, each line spells out "dividend = quotient × divisor + remainder", with the remainder in yellow because it becomes the next line's divisor; on the right, a table of the remainder sequence r and the quotients q. Blue marks the current step. After three divisions the remainder hits 0, the previous remainder 21 turns green, and lcm = 1260 falls out along the way. The second stage is extended Euclid: the table gains columns s and t, and every row satisfies r = 252·s + 105·t. Notice that s and t follow the same "row before last minus q times the last row" rule as r, and the final green row gives x = −2 and y = 5.

05Code

gcd, lcm, extended Euclid, and the modular inverse built on it. The Python extended version is recursive and lines up step for step with the substitution above; the C++ one is iterative — exactly the r, s, t table from the demo — and uses no call stack. Both end by showing how to fold over several numbers, and the versions the standard library already provides.

from functools import reduce


def gcd(a, b):
    """Euclidean algorithm: gcd(a, b) = gcd(b, a mod b). O(log min(a, b))"""
    a, b = abs(a), abs(b)
    while b:
        a, b = b, a % b                  # replace the larger with the remainder, until the remainder is 0
    return a


def lcm(a, b):
    """Least common multiple: divide before multiplying so nothing exceeds the answer"""
    if a == 0 or b == 0:
        return 0
    return abs(a // gcd(a, b) * b)


def ext_gcd(a, b):
    """Extended Euclid (a, b >= 0): returns (g, x, y) with a*x + b*y == g"""
    if b == 0:
        return a, 1, 0                   # a*1 + 0*0 == a
    g, x1, y1 = ext_gcd(b, a % b)        # b*x1 + (a % b)*y1 == g
    # substitute a % b == a - (a // b)*b and regroup as coefficients of a and b
    return g, y1, x1 - (a // b) * y1


def mod_inverse(a, m):
    """Inverse of a modulo m. m need not be prime, only gcd(a, m) == 1"""
    g, x, _ = ext_gcd(a % m, m)
    if g != 1:
        return None                      # not coprime, so no inverse exists
    return x % m                         # x may be negative, so pull it back into [0, m)


if __name__ == "__main__":
    print(gcd(48000, 44100))             # 300 (44.1 kHz → 48 kHz is the ratio 160/147)
    print(lcm(24, 30))                   # 120
    print(ext_gcd(252, 105))             # (21, -2, 5): 252·(−2) + 105·5 = 21
    print(mod_inverse(17, 3120))         # 2753 (the private exponent d from the RSA example)
    print(mod_inverse(6, 9))             # None (gcd(6, 9) = 3)
    print(reduce(gcd, [84, 126, 210]))   # 42: fold pairwise for more than two numbers
    print(reduce(lcm, [6, 8, 15]))       # 120
    # Built in: math.gcd, and math.lcm since Python 3.9; both accept several arguments

06Practice

• LeetCode 1979Find Greatest Common Divisor of ArrayEasy
• LeetCode 1071Greatest Common Divisor of Strings (the Euclidean algorithm on strings)Easy
• LeetCode 914X of a Kind in a Deck of Cards (gcd of all the counts)Easy
• LeetCode 592Fraction Addition and Subtraction (common denominator, then reduce)Medium
• LeetCode 365Water and Jug Problem (Bézout: measurable exactly when the gcd divides the target)Medium
• LeetCode 878Nth Magical Number (lcm plus binary search on the answer)Hard