CONCEPT · Master
GCD / LCM
also euclidean · greatest common divisor · lcm
gcd(a,b)=gcd(b,a mod b) in O(log a). Linear combinations are multiples of the gcd. lcm(a,b)=a/gcd*b — divide first.
Intuition
Subtracting multiples does not change the gcd. Euclid is just the fastest way to subtract.
When to reach for it
- Array gcd / make-equal-by-subtract
- Fractions, lattice points, frog jumps
- Bezout / modular inverse via extended Euclid
Usual pits
- a * b / gcd overflows; write a / gcd * b
- lcm of three is not product / gcd
- gcd(0,0) conventions
- Float remainders