GCD and the Euclidean Algorithm
The Greatest Common Divisor (GCD) is the largest number that divides both numbers evenly. Rather than listing and comparing divisors, the Euclidean algorithm computes it in O(log). The Least Common Multiple (LCM) follows immediately once you have the GCD.
The one-line idea: "shrink by replacing the larger number with the remainder." The two numbers get smaller via modulo, and the answer appears the moment the remainder hits 0.
The Key Property
gcd(a, b) = gcd(b, a mod b)
Reduce the problem using the remainder of a divided by b; when b becomes 0, the current a is the GCD.
Why does it hold? Writing a = q·b + r, the common divisors of a and b are exactly the common divisors of b and r (= a mod b) (dividing one side divides the other). So replacing (a, b) with (b, a mod b) preserves the GCD.
How It Works
Step 1. If b is 0, then a is the GCD (stop).
Step 2. Otherwise reduce to gcd(b, a mod b) and recurse (or loop).
Step 3. Repeat until the remainder is 0; the divisor left is the GCD.
The AlgoNote visualization shows how the two numbers shrink via modulo, step by step.
LCM from GCD
lcm(a, b) = a / gcd(a, b) × b
It's the product a × b divided by the GCD. But multiplying a × b first can overflow for large numbers, so divide first as a / gcd × b to stay safe.
Time and Space Complexity
| Complexity | |
|---|---|
| Time | O(log(min(a, b))) |
| Space | O(1) (iterative) |
Modulo shrinks the values fast each step, giving logarithmic time.
Walking Through an Example
gcd(48, 18):
- •gcd(48, 18) → 48 mod 18 = 12 → gcd(18, 12)
- •gcd(18, 12) → 18 mod 12 = 6 → gcd(12, 6)
- •gcd(12, 6) → 12 mod 6 = 0 → gcd(6, 0) = 6
So the GCD is 6, and lcm(48,18) = 48 / 6 × 18 = 144.
Common Mistakes
- •LCM overflow: multiplying
a × bfirst can exceed the type's range. Divide first. - •Handling 0: omitting the
gcd(a, 0) = arule breaks the termination condition. - •Negative inputs: usually handled by taking absolute values.
See It in Action on AlgoNote
Watch the larger number shrink via modulo until it reaches the GCD, step by step on AlgoNote.