Why it works: proofs, Euclid and the edges

You can now find an HCF or LCM four different ways, and you have discovered patterns by testing. This layer asks the questions a mathematician asks next: Why do the methods work? Are the patterns true for every number, or just the ones we tried? What happens at the edges?

The arguments here are short, but they are real proofs, the same ones found in university number theory books, written in plain language. Read them slowly, with a pencil. After each one, try it on your own example: a proof you have checked with numbers is a proof you understand.

The prime-factor method rests on one big fact:

Fundamental Theorem of Arithmetic. Every whole number greater than 1 can be written as a product of primes in exactly one way, apart from the order of the factors.

The first half (it can be done) is easy: keep splitting until you only have primes. The second half (only one way) is the surprising part. Why could 360 not be 2³ × 3² × 5 one way and something completely different another way?

The key step is a property of primes proved by Euclid: if a prime divides a product, it must divide one of the factors. For example, 7 | 21 × 10 = 210, and indeed 7 | 21. (A composite number does not have this property: 6 | 4 × 9 = 36, but 6 divides neither 4 nor 9.) With that property, if two prime recipes gave the same number, each prime in the first recipe would have to divide, and so equal, some prime in the second, and you could cancel them one pair at a time until nothing is left. The two recipes must be the same.

Uniqueness has a powerful consequence. Write 360 = 2³ × 3² × 5. A number divides 360 exactly when its recipe uses only 2, 3 and 5, with at most three 2s, at most two 3s and at most one 5. Nothing else can divide it, because any other prime, or an extra copy of one of these, would have to appear in 360's one and only recipe.

So each divisor is a choice: 0, 1, 2 or 3 twos (4 choices), 0, 1 or 2 threes (3 choices), 0 or 1 five (2 choices). That gives 4 × 3 × 2 = 24 divisors, which you can check by listing them.

Take a = 360 = 2³ × 3² × 5 and b = 588 = 2² × 3 × 7².

The HCF. A common divisor d must divide 360, so it has at most three 2s; and divide 588, so at most two 2s. It must satisfy both, so at most min(3, 2) = 2 twos. Similarly at most min(2, 1) = 1 three. It cannot contain 5 (588 has none) or 7 (360 has none). The biggest number obeying all these limits takes the maximum allowed of each: 2² × 3 = 12. That is the HCF, and it is the product of the common primes with the smallest powers.

The LCM. A common multiple m must contain 360's recipe, so at least three 2s, two 3s and one 5; and contain 588's recipe, so at least two 2s, one 3 and two 7s. It needs at least max(3, 2) = 3 twos, max(2, 1) = 2 threes, one 5 and two 7s. The smallest such number has exactly those: 2³ × 3² × 5 × 7² = 17,640.

Look at the last column of the table above: for every prime, min + max = the sum of the two powers. That is not a coincidence. For any two numbers x and y, one of them is the smaller and the other the larger, so min(x, y) + max(x, y) = x + y. (If x = 3 and y = 2: 2 + 3 = 3 + 2.)

Now multiply powers of the same prime by adding indices: 2² × 2³ = 2⁵.

• In HCF × LCM, the power of each prime p is min + max.
• In a × b, the power of each prime p is (power in a) + (power in b).

These are equal for every prime, so by the uniqueness of prime recipes, HCF(a, b) × LCM(a, b) = a × b. For 360 and 588: 12 × 17,640 = 2,11,680 = 360 × 588. ✓

That is a complete proof, for every pair of positive whole numbers, not just the ones we tested.

For strong learners, here is a formula that does work for three numbers. It corrects for the primes shared by exactly two of them:

LCM(a, b, c) = a × b × c × HCF(a, b, c) ÷ [HCF(a, b) × HCF(b, c) × HCF(c, a)]

Try it on 6, 10, 15: the product is 900, HCF(6, 10, 15) = 1, and the pairwise HCFs are 2, 5 and 3. So LCM = 900 × 1 ÷ 30 = 30. ✓ On 12, 18, 30: 6,480 × 6 ÷ (6 × 6 × 6) = 180. ✓ It can be proved prime by prime, like the two-number rule, using this fact about any three powers x, y, z: max(x, y, z) = x + y + z − min(x, y) − min(y, z) − min(z, x) + min(x, y, z). Try it with 1, 2, 3: 6 − 1 − 2 − 1 + 1 = 3. ✓

In Discover you noticed that the common multiples of 4 and 6 are 12, 24, 36, … : all multiples of the LCM. Here is a proof that avoids prime factors entirely and uses only division with remainder.

Let L = LCM(a, b) and let M be any common multiple of a and b. Divide M by L:

M = q × L + r, where the remainder r is 0, 1, 2, …, up to L − 1.

• a divides M and a divides L (so a divides q × L). Therefore a divides M − q × L = r.
• In the same way, b divides r.
• So r is a common multiple of a and b (or 0). But r is smaller than L, and L is the lowest positive common multiple. So r cannot be a positive common multiple: r must be 0.

Therefore M = q × L: every common multiple is a multiple of the LCM. ∎

Euclid’s method replaces the pair (a, b) by the pair (b, r), where a = q × b + r. Here is why the HCF does not change.

Claim. The pairs (a, b) and (b, r) have exactly the same common divisors.

• If d divides a and b, then d divides a − q × b = r. So d is a common divisor of b and r.
• If d divides b and r, then d divides q × b + r = a. So d is a common divisor of a and b.

Same common divisors means same greatest common divisor: HCF(a, b) = HCF(b, r).

Why it stops. Each remainder is smaller than the divisor before it, so the numbers keep getting smaller. Whole numbers cannot decrease for ever, so eventually a remainder is 0. At that point we have a pair (g, 0), and HCF(g, 0) = g, because every number divides 0. So the last non-zero remainder is the HCF. ∎

Try Euclid on two neighbouring Fibonacci numbers (1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …, each the sum of the two before). Every quotient is 1 and every remainder is the previous Fibonacci number:

89 = 55 × 1 + 34; 55 = 34 × 1 + 21; 34 = 21 × 1 + 13; … all the way down to 2 = 1 × 2 + 0.

That is 9 divisions for numbers under 100, the most for any pair that small. In 1844 the French mathematician Gabriel Lamé proved that this is the worst case: the number of division steps is never more than 5 times the number of digits in the smaller number. So even for numbers with 100 digits, Euclid needs at most 500 steps, which a computer does in a blink. Factorising two 100-digit numbers, by contrast, can be impossibly slow. That is why computers find HCFs by Euclid, not by prime factors.

Run Euclid’s steps backwards and something remarkable appears. For 252 and 198 the steps were:

252 = 198 × 1 + 54; 198 = 54 × 3 + 36; 54 = 36 × 1 + 18.

Now rewrite, starting from the last useful line and substituting upwards:

• 18 = 54 − 36
• 36 = 198 − 3 × 54, so 18 = 54 − (198 − 3 × 54) = 4 × 54 − 198
• 54 = 252 − 198, so 18 = 4 × (252 − 198) − 198 = 4 × 252 − 5 × 198

Check: 4 × 252 = 1,008 and 5 × 198 = 990, and 1,008 − 990 = 18. ✓

This always works: the HCF of a and b can be written as a × x + b × y for some whole numbers x and y (one of them negative). It is called Bézout’s identity, after Étienne Bézout (1730–1783) — although for whole numbers it was stated much earlier, by Claude Gaspard Bachet de Méziriac in 1624, and Bézout’s own proof was for polynomials. Earlier still, the Indian mathematician Aryabhata used the same back-substitution around 499 CE in his kuttaka ("pulveriser") method for solving equations like a × x − b × y = c.

The "divides the difference" principle lets you prove facts about infinitely many pairs at once. Use letters for the numbers, and subtract cleverly, exactly as Euclid would.

Example. Show that n and 2n + 1 are co-prime for every whole number n.

Any common divisor d of n and 2n + 1 also divides 2 × n, and so divides (2n + 1) − 2n = 1. The only divisor of 1 is 1. So HCF(n, 2n + 1) = 1, whatever n is. (Try n = 7: HCF(7, 15) = 1. n = 100: HCF(100, 201) = 1.)