The Least Common Multiple
The gcd
looks down at the divisors two numbers share. Its mirror image looks up at the
multiples they share. The smallest positive number that both a and
b divide is their least common multiple,
\operatorname{lcm}(a, b) — the first moment two repeating cycles line
back up.
From prime factorisations
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 multiple of both 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 formula
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.
Where it shows up
The lcm is the common denominator when adding fractions, and the period at which two cycles
re-synchronise — two gears with 12 and 18
teeth return to their start after 36 steps. That "when do the cycles
align?" question returns in force in the
Chinese Remainder Theorem.