The Least Common Multiple

Two buses pull out of the depot together at 9am. One comes back round every 4 minutes, the other every 6. When will they next arrive side by side again? That "when do two repeating cycles line up?" question — buses, blinking lights, planets, gears — is exactly what the least common multiple answers.

Count in 2s and you land on 2, 4, 6, 8, 10, \dots — the multiples of 2. Count in 3s and you land on 3, 6, 9, 12, \dots. Sooner or later the two counts land on the same number. The first number they share is the least common multiple — written \operatorname{lcm}(a, b).

The gcd looks down at the divisors two numbers share. The lcm is its mirror image: it looks up at the multiples they share, and picks the smallest one — the first moment two repeating cycles line back up.

Find it by listing multiples

The surest way for small numbers is to list the multiples of each until the same number appears in both lists. That first shared number is the lcm.

Example: \operatorname{lcm}(4, 6).

Both lists hit 12 first, so \operatorname{lcm}(4, 6) = 12. (They meet again at 24, and again at 36 — at every multiple of 12 — but 12 is the smallest, so it wins.)

The lcm is the smallest shared multiple, not the two numbers multiplied together.

See it: two skip-counts meeting

The top line jumps in steps of one size, the bottom line in another. Follow the dots until both lines land on the same number at the same time — that first shared landing is the lcm, ringed for you. Press Refresh for a new pair.

Adding fractions needs it

You can only add fractions once they share a denominator — and the tidiest one to use is the lcm of the two denominators, called the lowest common denominator.

\tfrac{1}{4} + \tfrac{1}{6} = \tfrac{3}{12} + \tfrac{2}{12} = \tfrac{5}{12}.

Because \operatorname{lcm}(4, 6) = 12, both quarters and sixths can be re-cut into twelfths exactly, with nothing left over — then the tops simply add.

bus bus

The red bus leaves every 4 minutes; the blue bus every 6 minutes. They pull out together now — when will they next leave together? Not in 4 minutes (only red), not in 6 (only blue), but at \operatorname{lcm}(4, 6) = 12 minutes, when both their cycles come back into step. After that, every 12 minutes again.

frog frog

One frog hops 3 pads at a time and lands on 3, 6, 9, 12, \dots The other hops 5 at a time and lands on 5, 10, 15, \dots The first pad they both touch is 15 = \operatorname{lcm}(3, 5). Since 3 and 5 share no factors, the meeting point is just 3 \times 5 — the only time multiplying is the shortcut.

From prime factorisations

For bigger numbers, listing is slow. Instead, split each number into prime factors. Where the gcd takes the smaller power of each prime, the lcm takes the larger:

12 = 2^2 \cdot 3, \qquad 18 = 2 \cdot 3^2 \operatorname{lcm}(12,18) = 2^{\max(2,1)} \cdot 3^{\max(1,2)} = 2^2 \cdot 3^2 = 36.

Every shared multiple must contain enough of each prime to be divisible by either number — so it needs the larger power. Take exactly the larger power and no more, and you get the smallest such number.

The product shortcut

Because \min(e, f) + \max(e, f) = e + f for every exponent, the gcd and lcm together account for all the prime factors of both numbers. This gives a wonderfully simple link:

For positive integers a and b,

\gcd(a, b) \cdot \operatorname{lcm}(a, b) = a \cdot b.

So you never need to factorise to find an lcm: run the fast Euclidean algorithm for the gcd, then divide.

\operatorname{lcm}(12, 18) = \frac{12 \cdot 18}{\gcd(12,18)} = \frac{216}{6} = 36.

And the same "when do the cycles align?" question — two gears with 12 and 18 teeth return to their start after 36 steps — returns in force in the Chinese Remainder Theorem.

See it explained