16. Casting out nines.
This large cross was used for hundreds of years: Figure 17 shows its use by the 16th-century German Rechenmeister (master of ‘reckoning’) Adam Riese, and in an arithmetical calculation by Abraham Lincoln. Eventually the cross decreased in size and became the multiplication sign that we use today.
17. A German postage stamp commemorates Adam Riese. An example from Abraham Lincoln’s ‘Cyphering book’.
Chapter 3Prime-time mathematics
As we saw in Chapter 1, prime numbers lie at the heart of number theory, and we’ll now explore some of their properties. We’ll see how to generate prime numbers and show that the list of primes is never-ending. We’ll see that there’s essentially just one way of splitting any given number into its prime factors, and we’ll introduce some important types of primes. Our explorations will spill over into Chapter 7 where we’ll describe some more general issues, such as how the prime numbers are distributed and whether we can find progressions of equally spaced prime numbers.
We recall from Chapter 1 that a prime number is a number, greater than 1, whose only factors (divisors) are itself and 1, and a number that’s not prime is composite. A list of all the prime numbers up to 1000 appears in Table 1. Notice that some primes appear to cluster quite closely together, such as 101, 103, 107, and 109, whereas others, such as 113 and 127, are more widely spaced.
Table 1. The prime numbers up to 1000
The sieve of Eratosthenes
How might we generate such a list of prime numbers? An early method was to use the sieve of Eratosthenes, named after Eratosthenes of Cyrene who lived in the 3rd century bc and is also celebrated for estimating the circumference of the Earth. His idea was to imagine putting the positive integers into a sieve and letting all the composite numbers fall though the holes, leaving just the primes. For example, to produce the above table of primes up to 1000 we list all the numbers from 2 to 1000 and then systematically sift out the multiples of 2, then the multiples of 3, and then those of 5, 7, 11, … for each successive prime number.
To see how this sifting process works in practice, we’ll find all the primes up to 100. We start by listing all the numbers up to 100 and cross out 1. We then leave in 2, but cross out all its larger multiples—that is, 4, 6, 8, …, 98, 100. This gives us the following table:
We then leave in the next number, which is 3, but cross out those of its larger multiples that remain—that is, 9, 15, 21, …, 93, 99. Note that the other multiples of 3, such as 6, 12, and 18, were already crossed out at the previous stage.
Repeating the process for the larger multiples of 5, and then 7, leaves:
At this stage we might worry that this sifting process could take a long time to complete, but this isn’t the case: every multiple of 11 (other than 11 itself) has already been crossed out, as has every multiple of 13 and of all larger primes, so we already have our full list of primes up to 100. We don’t need to check the multiples of any primes above 10, because if a number from 2 to 100 has a prime factor p that’s greater than 10, then it must also have a prime factor q that’s less than 10; this is because if q were also greater than 10, then would be greater than 100.
In general, to find all the primes up to a given number n we need to cross out only the larger multiples of the primes up to its square root, √n. For example, to find all the primes up to 200 we cross out only the larger multiples of the primes up to (these are the primes 2, 3, 5, 7, 11, and 13), and to find all the primes up to 1000 we cross out only the larger multiples of the primes up to √1000 (these are the primes up to 31).
Primes go on for ever
The list of prime numbers continues for ever: there is no largest prime. As we mentioned in Chapter 1, this was proved in the 3rd century bc by Euclid in Book IX of his Elements:
There are infinitely many primes.
At first sight it may seem difficult to see how we might attempt to prove such a result, because if we’re given a specific prime number, such as 997, it’s not immediately obvious what the next prime would be. (It’s actually 1009.)
Euclid’s proof of his theorem is considered one of the great classics of mathematics, and is a proof by contradiction (sometimes called reductio ad absurdum). This means that we suppose the opposite result—that there are only finitely many primes—and then show how that supposition leads us to a contradictory statement. His method was based on the fact that, given any collection of primes, we can always find a new one and so, by continually repeating this process with the new list, we can carry on generating new primes for ever. This contradiction establishes the result.
To illustrate the idea behind this process we’ll take a collection of prime numbers, multiply them together, add 1, and then look at the resulting number. For example, if we start with 2, 3, and 5, we have
which is a prime number that wasn’t in our original list. Or if we start with 2, 5, and 11, we have
which isn’t a prime number but which splits as , giving us two new primes: 3 and 37.
