Least common multiple

Content sourced from Wikipedia, licensed under CC BY-SA 3.0.

Least common multiple (LCM) is the smallest positive number that is a multiple of each given number. For two integers a and b, it’s the smallest positive number divisible by both. For more numbers, it’s the smallest positive number divisible by all of them. The LCM ignores signs, so lcm(-4,6) = lcm(4,6) = 12. If one number is zero, the LCM is usually defined as 0 (and lcm(0,0) is a special case that’s also 0).

Examples:
- lcm(4, 6) = 12
- lcm(8, 9, 21) = 504
- lcm(-5, -2) = 10

How to compute the LCM:
- Using gcd (greatest common divisor): lcm(a, b) = |a × b| / gcd(a, b). To keep numbers smaller, you can compute it as (a / gcd(a, b)) × b.
- The gcd can be found quickly with the Euclidean algorithm.
- Prime factorization method: write a and b as products of primes with exponents, a = ∏ p^ap and b = ∏ p^bp. The LCM uses the highest exponent of each prime: lcm(a, b) = ∏ p^max(ap, bp). This works but is slower for large numbers.

For more than two numbers, use lcm(a, b, c, ...) = lcm(lcm(a, b), c, ...). The LCM is also useful for turning fractions into a common denominator, and it appears in problems like gear alignments and orbital periods, where systems repeat at common multiples.

In short, the LCM finds the smallest number that all given numbers divide into, making it handy for combining multiples and fractions.