GCD and LCM: the two numbers that simplify and synchronise

Two whole numbers have two useful relationships. The greatest common divisor is the largest number that divides both of them exactly. The least common multiple is the smallest number they both divide into. One simplifies fractions; the other answers "when do these two cycles line up again?" — and they are computed from each other.

Finding the GCD without guessing

You could list every factor of both numbers and look for the biggest shared one. That works for small numbers and becomes hopeless quickly. Euclid's algorithm is better and is about 2,300 years old: divide the larger by the smaller, keep the remainder, and repeat with the smaller number and that remainder until the remainder is zero. The last non-zero number is the GCD.

For 24 and 36:

1. 36 ÷ 24 leaves remainder 12.
2. 24 ÷ 12 leaves remainder 0.

The last non-zero remainder is 12, so GCD(24, 36) = 12. Two steps, no factor lists.

The LCM comes free

Once you have the GCD you never compute the LCM separately, because of a fact that holds for every pair of whole numbers: GCD × LCM = a × b. Rearranged, LCM = (a × b) ÷ GCD.

For our pair: (24 × 36) ÷ 12 = 864 ÷ 12 = 72. So LCM(24, 36) = 72. Worth sanity-checking: 72 is 3 lots of 24 and 2 lots of 36. Both divide it exactly, and nothing smaller does.

Using the GCD: simplifying a fraction

To reduce a fraction to its simplest form, divide the top and bottom by their GCD. Take 18/48:

1. 48 ÷ 18 leaves remainder 12.
2. 18 ÷ 12 leaves remainder 6.
3. 12 ÷ 6 leaves remainder 0 — so the GCD is 6.

Then 18 ÷ 6 = 3 and 48 ÷ 6 = 8, giving 3/8. Dividing by the greatest common divisor is what gets you there in one move; dividing by any smaller shared factor just means going round again. (And 3/8, as it happens, is 0.375 as a decimal.)

Using the LCM: when do two cycles coincide?

One bus leaves every 12 minutes, another every 18, and both have just departed. When do they next leave together?

GCD(12, 18): 18 ÷ 12 leaves 6; 12 ÷ 6 leaves 0, so the GCD is 6. Then LCM = (12 × 18) ÷ 6 = 216 ÷ 6 = 36 minutes. Check it: the first bus goes at 12, 24, 36; the second at 18, 36. They coincide every 36 minutes.

The same question wearing different clothes covers a lot of ground: two maintenance schedules at 8 and 14 weeks, shift patterns, gear teeth meshing, a payroll cycle against a billing cycle. Any two things that repeat on fixed intervals realign at the LCM of those intervals.

When the numbers share nothing

If the GCD is 1 the numbers are called coprime, and it tells you two things at once. The fraction is already in its simplest form and cannot be reduced. And the LCM is just the two numbers multiplied — (a × b) ÷ 1 — so the cycles take as long as possible to realign. Bus intervals of 12 and 18 realign in 36 minutes; intervals of 11 and 13 take 143.

That is not a curiosity. It is why gear designers often choose coprime tooth counts: the same pair of teeth then meet as rarely as possible, spreading wear evenly instead of concentrating it.

Run your own numbers

The free GCD & LCM calculator runs Euclid's algorithm and the LCM identity on any two whole numbers, entirely on your device.