GCD
—
Greatest Common Divisor
LCM
—
Least Common Multiple
Definitions
- GCD (Greatest Common Divisor): the largest positive integer that divides all the given numbers without remainder
- LCM (Least Common Multiple): the smallest positive integer that is divisible by all the given numbers
- Relationship: GCD(a,b) × LCM(a,b) = a × b
- Euclidean algorithm: GCD(a,b) = GCD(b, a mod b), eventually reaches GCD(x,0) = x
Use cases
- Simplify fractions: divide numerator and denominator by GCD
- Find common denominator: use LCM of all denominators
- Synchronize cyclic events (when do two cycles align?)
- Cryptography (RSA key generation uses GCD)