Why it all works: proofs about primes

In the earlier layers you used facts about primes: every number splits into primes; you only test up to the square root; digit sums test for 3 and 9; there are infinitely many primes. This layer asks the question a mathematician always asks next: why?

You will meet some of the most beautiful short arguments in mathematics, several of them over 2,000 years old. None needs more than multiplication, division and careful thinking. The aim is not to memorise these arguments but to understand them well enough to explain them to someone else, and to know exactly where each one would break if a small detail were changed.

Claim: every counting number bigger than 1 is either prime or a product of primes.

Why: take any number n bigger than 1. Look at its smallest factor that is bigger than 1; call it p.

• p must be prime. If p were composite, it would have a smaller factor bigger than 1, and that smaller factor would also divide n. But p was the smallest. Contradiction.
• So n = p × m for some m. If m = 1, then n = p is prime and we are done. Otherwise, m is smaller than n, and we repeat the same step on m.
• The numbers keep getting smaller (n, then m, then …), and a sequence of counting numbers cannot shrink forever. So the process stops, and when it does, we have written n as a product of primes.

This is exactly what a factor tree or division ladder does. The argument shows it always finishes.

In Understand you saw that 60 always ends up as 2 × 2 × 3 × 5, however you start the tree. This is not luck. It is a theorem so important that it is called the Fundamental Theorem of Arithmetic:

Every counting number bigger than 1 can be written as a product of primes in exactly one way, apart from the order of the factors.

Chapter 1 proved the "can be written" part. The "exactly one way" part rests on a key fact about primes, first written down by Euclid:

Euclid's lemma. If a prime p divides a product a × b, then p divides a or p divides b (or both).

For example, 7 divides 42 × 5 = 210, and 7 divides 42. 3 divides 4 × 15, and 3 divides 15. This is false for composites: 6 divides 4 × 9 = 36, but 6 divides neither 4 nor 9. The 2 in 6 hides in the 4 and the 3 hides in the 9. A prime cannot be split up like that.

Why uniqueness follows: suppose a number had two different prime recipes. Take any prime p in the first recipe. It divides the number, so by Euclid's lemma (used repeatedly) it divides one of the primes in the second recipe. But a prime's only factors are 1 and itself, so p must be that prime. Cancel it from both recipes and repeat. Every prime pairs off, so the recipes were the same all along.

Uniqueness is not automatic. To see why it is special, imagine a world where the only numbers are the even numbers 2, 4, 6, 8, … In that world, call an even number an "E-prime" if it cannot be written as a product of two smaller even numbers.

• 4 = 2 × 2, 8 = 2 × 4 and 12 = 2 × 6 are not E-prime.
• 2, 6, 10, 14, 18, 22, 26, 30, … (the numbers that leave remainder 2 when divided by 4) are E-prime: two even numbers multiply to a multiple of 4, so these can never be made.

Now factorise 60 in the even world: 60 = 2 × 30 and 60 = 6 × 10. Both are products of E-primes, and they are different! Also 180 = 2 × 90 = 6 × 30 = 10 × 18. In the even world, factorisation is not unique. Our ordinary numbers are special because Euclid's lemma holds for them.

Once a number is written in index form, many questions become quick.

Which numbers divide it? A number d divides n exactly when every prime in d appears in n at least as many times. So 12 = 2² × 3 divides 360 = 2³ × 3² × 5, but 16 = 2⁴ does not (360 has only three 2s).

How many factors? Every factor of 360 is 2^a × 3^b × 5^c, where a can be 0, 1, 2 or 3 (4 choices), b can be 0, 1 or 2 (3 choices) and c can be 0 or 1 (2 choices). Different choices give different factors (because factorisation is unique!), so there are 4 × 3 × 2 = 24 factors. In general, add 1 to each power and multiply.

Is it a perfect square? A square has every power even: 3,600 = 2⁴ × 3² × 5² = 60 × 60. That is why squares have an odd number of factors: each (even power + 1) is odd, and odd × odd × … is odd.

Is it a perfect cube? Every power is a multiple of 3: 7,776 = 2⁵ × 3⁵ is not a cube, but 2⁶ × 3³ = 1,728 = 12 × 12 × 12 is.

Claim: if n is composite, then n has a prime factor p with p × p ≤ n.

Why: n composite means n = a × b, where a and b are both bigger than 1 and a ≤ b. Then a × a ≤ a × b = n. So a ≤ √n. The smallest prime factor of a is at most a, and it divides n too. So n has a prime factor no bigger than √n.

Turned round: if no prime up to √n divides n, then n cannot be composite, so it is prime. That is the trial-division rule.

The same argument explains the sieve. When you sieve with a prime p, every multiple k × p with k smaller than p has a prime factor smaller than p (a factor of k), so it was already crossed out. The first multiple p has to deal with is p × p. And once p × p passes the end of the grid, there is nothing left to do.

Every divisibility rule comes from two facts.

1. Place value. 7,128 means 7 × 1,000 + 1 × 100 + 2 × 10 + 8.
2. Sharing a divisor. If d divides two numbers, it divides their sum and their difference. So if d divides one part of a number, d divides the whole exactly when it divides the rest.

Rules for 2, 5 and 10. 10 = 2 × 5, so every multiple of 10 is divisible by 2, 5 and 10. Write 7,128 = 7,120 + 8. The 7,120 part is a multiple of 10, so only the last digit, 8, decides. 8 is even, so 7,128 is divisible by 2 but not by 5 or 10.

Rule for 4. 100 = 4 × 25, so every multiple of 100 is divisible by 4. Write 7,128 = 7,100 + 28. Only the last two digits decide: 28 = 4 × 7. ✓ (The same reasoning gives a rule for 25: look at the last two digits.)

Rule for 8. 1,000 = 8 × 125. Write 15,128 = 15,000 + 128. Only the last three digits decide: 128 = 8 × 16. ✓

Rules for 3 and 9. The key fact is that 10 is one more than 9. So

• 10 = 9 + 1
• 100 = 99 + 1
• 1,000 = 999 + 1

and 9, 99, 999, … are all multiples of 9 (and of 3). Now write 7,128 like this:

7 × 1,000 + 1 × 100 + 2 × 10 + 8 = 7 × (999 + 1) + 1 × (99 + 1) + 2 × (9 + 1) + 8 = (7 × 999 + 1 × 99 + 2 × 9) + (7 + 1 + 2 + 8).

The first bracket is a multiple of 9. The second bracket is the digit sum, 18. So 7,128 and its digit sum leave the same remainder when divided by 9 (or by 3). Divisible by 9 exactly when the digit sum is. That is also why a number minus its reverse (same digits, same digit sum) is always a multiple of 9.

Rule for 11. Here the key fact is that 10 is one less than 11. So

• 10 = 11 − 1
• 100 = 99 + 1, and 99 = 9 × 11
• 1,000 = 1,001 − 1, and 1,001 = 91 × 11
• 10,000 = 9,999 + 1, and 9,999 = 909 × 11

The powers of 10 are alternately 1 more and 1 less than a multiple of 11. So a number leaves the same remainder on division by 11 as its digits added with alternating signs, starting with + on the units digit. For 9,284: 4 − 8 + 2 − 9 = −11, a multiple of 11, so 9,284 = 11 × 844. ✓

Rule for 6. 6 = 2 × 3 and 2, 3 are co-prime. If a number is divisible by 2 and by 3, its prime factorisation contains a 2 and a 3, so it contains 6. With non-co-prime pieces, like 2 and 4, the 2 in 4 might be the same 2, which is why 12 passes both tests for 2 and 4 but fails for 8.

There is no digit-sum test for 7, because 10 is neither 1 more nor 1 less than a multiple of 7. But there are two good tricks.

Chop and double. Remove the last digit, double it, and subtract it from what is left. Repeat until the number is small. The original is divisible by 7 exactly when the result is.

Why it works: write the number as 10a + b (b is the last digit). The trick gives a − 2b. Now 2 × (10a + b) = 20a + 2b, and 20a + 2b + (a − 2b) = 21a, a multiple of 7. So 10a + b and a − 2b are either both multiples of 7 or neither (7 does not divide 2).

Use 1,001. 1,001 = 7 × 11 × 13. Split the number into groups of three digits from the right and add and subtract them alternately (because 1,000 is one less than 1,001). The result is divisible by 7, 11 or 13 exactly when the original is. For 7,028,011: 11 − 28 + 7 = −10, so it is not divisible by 7, 11 or 13.

Around 300 BCE, the Greek mathematician Euclid of Alexandria wrote the Elements, a set of thirteen books that was used to teach mathematics for over 2,000 years. In Book IX he proved that there is no largest prime. His argument is short enough to fit on a postcard.

Claim: there are more primes than any list you can make.

Why: suppose someone hands you a finite list of primes, say 2, 3, 5 and 7. Multiply them all together and add 1:

N = 2 × 3 × 5 × 7 + 1 = 211.

Now look at N.

• Dividing N by 2 leaves remainder 1 (N is one more than a multiple of 2).
• Dividing N by 3 leaves remainder 1. The same happens for 5 and for 7.
• So none of the primes on the list divides N.
• But N is bigger than 1, so it has at least one prime factor (Chapter 1).
• That prime factor is therefore not on the list.

The list was missing a prime. This works for any finite list, so no finite list can contain every prime. There are infinitely many primes.

A second proof, found in 2006. The mathematician Filip Saidak noticed a proof that uses only one fact from this topic: consecutive numbers are co-prime.

Start with any number, say 2. Multiply it by the next number: 2 × 3 = 6. Since 2 and 3 are co-prime, 6 has at least two different prime factors.

Now do it again with 6: 6 × 7 = 42. Since 6 and 7 are co-prime, 7 brings at least one prime that is not in 6. So 42 has at least three different prime factors (2, 3, 7).

Again: 42 × 43 = 1,806 = 2 × 3 × 7 × 43. At least four primes. Then 1,806 × 1,807 has at least five, because 1,807 = 13 × 139 shares no prime with 1,806.

Each step adds at least one new prime, and you can take as many steps as you like. So there must be infinitely many primes.

Co-prime means no shared prime. By unique factorisation, the common factors of two numbers are built from the primes they share. So HCF = 1 exactly when their factorisations have no prime in common. 8 = 2³ and 15 = 3 × 5 share no prime, so they are co-prime. That is the fastest test.

Consecutive numbers are co-prime. If d divides both n and n + 1, it divides their difference, 1. So d = 1.

The product rule. If a and b are co-prime and both divide n, then a × b divides n. Reason: a's primes appear in n, and b's primes appear in n; since they share no primes, they are different primes and all of them appear in n together. This is exactly why the test for 6 (2 and 3), 12 (3 and 4), 15 (3 and 5), 18 (2 and 9) and 24 (3 and 8) works, and why it fails for non-co-prime pieces.

Fractions in lowest terms. A fraction like 8⁄15 is in its simplest form exactly when the top and bottom are co-prime.

Nobody can prove that twin primes go on forever, but several facts about them are easy to prove.

1. After (3, 5), twin primes are 6k − 1 and 6k + 1. The middle number of twins p and p + 2 is even (it lies between two odd numbers). One of p, p + 1, p + 2 is a multiple of 3, and it cannot be p or p + 2 (they are primes bigger than 3). So the middle is a multiple of 2 and of 3, and since 2 and 3 are co-prime, a multiple of 6.

2. The sum of twin primes (after 3, 5) is a multiple of 12. p + (p + 2) = 2 × (p + 1) = 2 × 6k = 12k. Check: 17 + 19 = 36 = 12 × 3; 71 + 73 = 144 = 12 × 12.

3. The product of twin primes, plus 1, is a perfect square. p × (p + 2) + 1 = p × p + 2 × p + 1 = (p + 1) × (p + 1). Check: 11 × 13 + 1 = 144 = 12 × 12; 29 × 31 + 1 = 900 = 30 × 30.

4. The only prime triplet is 3, 5, 7. One of n, n + 2, n + 4 is always a multiple of 3 (check the three possible remainders), so for all three to be prime, that one must be 3.