Basics 0/129

Numbers and arithmetic · 2 of 4 Advanced

GCD and LCM

Find the greatest common divisor with Euclid's remainder steps, see why they work and how few they are, and compute the least common multiple without overflow.

2,388 words · 11 min read

Part 1 of 6 Greatest common divisor

The greatest common divisor of two numbers

Suppose we have two ribbons, 84 cm and 30 cm long, and want to cut both into pieces of one length, a whole number of centimetres, with nothing left over. We want the pieces as long as possible. A length works for a ribbon when it divides the ribbon's length, so it has to divide both 84 and 30. A number that divides both is a common divisor of the two, and the largest one is their greatest common divisor, written gcd⁡(84,30)\gcd(84, 30).

For numbers this small we can list the divisors of each and compare the lists:

Divisors of 84 and of 30
NumberDivisors
841, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42, 84
301, 2, 3, 5, 6, 10, 15, 30
In both lists1, 2, 3, 6

So gcd⁡(84,30)=6\gcd(84, 30) = 6: the long ribbon makes 84/6=1484 / 6 = 14 pieces and the short one 30/6=530 / 6 = 5. The same number reduces a fraction to lowest terms. Dividing the top and bottom of 3084\frac{30}{84} by 6 gives 514\frac{5}{14}, and no further reduction is possible, because 5 and 14 have no common divisor except 1. Two numbers whose gcd is 1 are called coprime.

Comparing lists means trying every candidate up to the smaller number against both numbers. That is 60 divisions for the ribbons, but contest inputs go up to 10910^9 and beyond, and a pair near 10910^9 would take about 2×1092 \times 10^9 divisions. At the rule-of-thumb rate of 10810^8 simple operations a second, that is twenty seconds for one gcd. The method in the next part finds the ribbons' answer in three divisions, and a pair below 10910^9 takes it at most 43, as the cost section further down works out.