Least Common Multiple (LCM)
What You'll Learn
You'll learn what the least common multiple is and how it relates to the greatest common divisor through an elegant product formula.
The Core Idea
The least common multiple (LCM) of two positive integers a and b is the smallest positive integer that is divisible by both a and b. In other words, it's the smallest number that both numbers "fit into" evenly.
For example, consider 12 and 18:
- Multiples of 12: 12, 24, 36, 48, 60, 72...
- Multiples of 18: 18, 36, 54, 72, 90...
The common multiples are 36, 72, 108, etc., and the least of these is 36. So LCM(12, 18) = 36.
The LCM-GCD Product Formula
Here's the beautiful connection: for any positive integers a and b,
LCM(a, b) × GCD(a, b) = a × b
This means you can find the LCM if you know the GCD:
LCM(a, b) = (a × b) / GCD(a, b)
Why This Works
Think of it this way: when you multiply two numbers, you're counting all their prime factors (with repetition). The GCD contains the prime factors they share, while the LCM contains each prime factor to the highest power it appears in either number. Together, GCD and LCM account for exactly the same prime factors as multiplying the original numbers.
For our example: 12 × 18 = 216, and GCD(12, 18) = 6, so LCM(12, 18) = 216/6 = 36 ✓
This formula is incredibly useful because computing GCD via the Euclidean Algorithm is efficient, making LCM computation efficient too.
Key Takeaway: The least common multiple is the smallest number divisible by both inputs, and it can be computed efficiently using LCM(a, b) = (a × b) / GCD(a, b).