GCD & LCM

The Euclidean algorithm: gcd(a, b) = gcd(b, a mod b) until b hits 0.

Why it works:

Any common divisor of a and b also divides a mod b — so the remainder chain preserves the answer while shrinking the numbers.

Its core advantage:

O(log min(a, b)) — even for astronomically large inputs.

Focus on recognizing:

Divisibility language (“common divisor”, “coprime”, “simplify”) = GCD

Core Template

public long gcd(long a, long b) {
    while (b != 0) {
        long t = a % b;
        a = b;
        b = t;
    }
    return a;
}

public long lcm(long a, long b) {
    return a / gcd(a, b) * b;   // divide FIRST — avoids overflow
}

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

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

long long gcd(long long a, long long b) {
    while (b) {
        long long t = a % b;
        a = b;
        b = t;
    }
    return a;
}

long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b;   // divide FIRST
}

function gcd(a, b) {
  while (b !== 0) {
    [a, b] = [b, a % b];
  }
  return a;
}

function lcm(a, b) {
  return (a / gcd(a, b)) * b; // divide FIRST
}

Everything else is this loop plus problem-specific bookkeeping.

Pattern 1: GCD of an Array

Watch (48, 18) shrink through the remainder chain to gcd = 6, then produce lcm = 144. Press ▶ to animate.

                        1
                        while b != 0:   (a, b) = (b, a mod b)
                      
                        2
                        gcd = a
                      
                        3
                        lcm = x * y / gcd        // divide FIRST to avoid overflow
                      

Fold the pairwise gcd:

public int arrayGcd(int[] nums) {
    int g = 0;
    for (int x : nums) g = (int) gcd(g, x);
    return g;   // gcd(0, x) = x — safe seed
}

from functools import reduce

def array_gcd(nums):
    return reduce(gcd, nums, 0)

int arrayGcd(vector<int>& nums) {
    int g = 0;
    for (int x : nums) g = std::gcd(g, x);
    return g;
}

function arrayGcd(nums) {
  return nums.reduce((g, x) => gcd(g, x), 0);
}

Array GCD = fold pairwise gcd, seeded with identity 0.

Pattern 2: Extended GCD (Bézout)

When you need coefficients: a·x + b·y = gcd(a, b) — used for modular inverses without prime modulus.

ext(b, a mod b) returns (x1, y1)
then x = y1,  y = x1 - (a / b) * y1

Know it exists for interviews; most problems only need plain gcd.

Common Mistakes

Computing LCM as a * b / gcd.

a * b overflows before the division. Always a / gcd * b.

Wrong identity when folding.

Seed with 0, not 1: gcd(0, x) = x. Seeding with 1 forces every answer to 1.

Assuming negative inputs behave.

Euclid on negatives can return negative results — take absolute values first if inputs may be negative.

Complexity