Number Theory: A Very Short Introduction
Page 5
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 3
Prime-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. In each case we’ve generated at least one new prime number that wasn’t in our original list.
A more formal proof is as follows. We’ll suppose that there are finitely many primes, which we’ll call p1, p2, …, and pn, and we’ll form the number
Now, each of these primes divides their product, , and so cannot also divide N because this would leave a remainder of 1. So either N is a new prime, or N is a composite number in which case it must split into new primes. In either case, there must exist a prime that’s different from p1, p2, …, and pn, and this contradicts our assumption that these were the only primes. Our original assumption must therefore be false, and so there are infinitely many primes.
Factorizing into primes
Earlier I mentioned that the prime numbers are the building blocks for our counting system, and we’ll now explore this idea further.
Starting from any collection of primes, we can build up further numbers by multiplication: for example, beginning with the primes 2 and 3 we can construct the numbers
and any other number of the form , where and .
Turning things around, we see that every integer greater than 1 splits into primes, because if the number n is composite then we can write for smaller integers a and b: for example, . If a is composite, then we can split it up further, and similarly for b. Continuing in this way, after a finitely many steps we’ll eventually obtain n as a product of primes.
Moreover, if we’re given a number such as 108, then we can split it up in more than one way: for example,
In the same way, we can write
We can illustrate all these factorizations as tree diagrams (see Figure 18).
18. Factorizations of 108 and 630.
In each case the prime factors at the lower ends of the trees are exactly the same, but they appear in a different order. This suggests the following result, which is known as the ‘fundamental theorem of arithmetic’. Although it must have been familiar to mathematicians for hundreds of years, it seems not to have been proved formally until Gauss did so in his Disquisitiones Arithmeticae of 1801.
Fundamental theorem of arithmetic: Every integer greater than 1 is either a prime number or can be written as a product of primes. Moreover, there is only one factorization into its prime factors, apart from the order in which they appear.
We can now see why we don’t wish 1 to be a prime number—for, if it were, then we could write, for example,
so that the uniqueness of the prime factorization would be lost.
Using the fundamental theorem of arithmetic, we can now write every positive integer as a product of primes in a standard way, by listing its prime factors in increasing order of size, with each one raised to the appropriate power: for example,
In general, if the prime factors of the number n are p1, p2, …, and pr, where each prime pi is raised to the power ei and the primes are listed in increasing order, then we write
This is called the canonical form of the prime
factorization of n, and we’ll often write prime factorizations in this way.
To conclude this section we’ll return briefly to least common multiples and greatest common divisors. In Chapter 2 we showed that and by listing the multiples and divisors of 90 and 54. But a quicker method is to write each number as a product of primes in canonical form:
where the extra factor 50 (which equals 1) is introduced so that the primes that appear (2, 3, and 5) are the same. Then:
to find lcm (90, 54), we look at each prime factor in turn, take the larger power that appears—that is, 21, 33, and 51—and multiply them to give ;
to find gcd (90, 54), we look at each prime factor in turn, take the smaller power that appears—that is, 21, 32, and 50—and multiply them to give .
In general, if a and b are written in canonical form as
(where we introduce the exponent 0 whenever a particular prime doesn’t appear), then
where max (e, f) is the larger of e and f, and
where min (e, f) is the smaller of e and f.
We can now revisit a result from Chapter 2—that, for any numbers a and b,
To explain why this is true we note first that, for any numbers e and f,
—for example, . Then the power of the first prime factor p1 on the left-hand side of the result that we’re trying to prove is
which is the power of p1 on the right-hand side. So the powers of p1 on the two sides match, and the same is true for all the other prime factors. So the two sides are equal.
Searching for primes
Are there any formulas for producing primes? Here are some historical attempts at finding them.
Euler’s primes
Leonhard Euler was obsessed with prime numbers, as we’ll see throughout this book. In 1771 he investigated the formula
and made the surprising observation that if we substitute every number n from 1 to 40 in turn, then we always get primes:
and so on, up to
These are all prime numbers, but the formula may also fail to produce primes: for example,
Likewise, the formula
produces prime numbers for every number n from 1 to 79, but not for 80 or many larger numbers. So neither of these formulas always gives primes.
Mersenne primes
Particularly important among the prime numbers, for reasons that will soon become clear, are those that are one less than a power of 2, such as
Numbers of the form are called Mersenne numbers and, as we saw in Chapter 1, not all of them are prime. To explore which ones have this property, let’s draw up a table of the first few Mersenne numbers.
Table 2. Numbers of the form
It may seem tempting, on looking at these numbers, to speculate that is a prime number when n is prime, and that it’s composite when n is composite. It’s certainly true that
is composite when n is composite,
because if r divides n (where ), then it can be shown that must divide , and so is composite: for example, when and , we have
But it isn’t always true that is prime when n is prime: for example,
Mersenne studied these numbers in 1644, and claimed that is prime for each of the values
The fact that is prime was first confirmed by Euler in 1750, and in 1876 the French mathematician Edouard Lucas showed that the following 39-digit Mersenne number is also prime:
So Mersenne was correct when and . But he was wrong in the cases and , both of which give composite numbers: for example,
He omitted the cases , , and , which also give rise to primes, but when we consider the large numbers involved, he may surely be forgiven. A method for testing whether a given Mersenne number is prime is given in the next chapter.
There’s an amusing story about the number . For many years mathematicians had struggled to determine whether this number is prime, as Mersenne had claimed, and in 1875 Lucas showed that it was composite but couldn’t find its factors. It was Frank Nelson Cole, a professor at Columbia University in New York, who found them after three years of systematic searching on Sunday afternoons. He presented his results on 31 October 1903 at a meeting of the American Mathematical Society, when he quietly walked into the lecture room and in complete silence painstakingly calculated 267 and subtracted 1 on one side of the blackboard. He then walked over to the other side of the board and, again in complete silence, calmly multiplied the numbers 193,707,721 and 761,838,257,287, obtaining the same answer, and quietly returned to his seat. The audience erupted and gave him a standing ovation and vigorous applause. At no stage had he uttered a single word!
Why are Mersenne primes important? In the continuing search for new and larger prime numbers it’s been usual to turn to Mersenne numbers, because all recently discovered large primes have been of this form—there’s even been a postage stamp celebrating the discovery of one of them (see Figure 19). Indeed, in recent years a new international collaborative online project has developed to track down such numbers. Involving thousands of mathematicians and computer enthusiasts, it’s called GIMPS (the Great Internet Mersenne Prime Search), and since it started around 1996 it has found seventeen of them. It’s not known whether there are infinitely many Mersenne primes.
19. A postage stamp celebrates the discovery in 2001 of the 39th Mersenne prime.
At the time of writing, fifty-one Mersenne primes have been found. The most recent of these, the largest prime number currently known, was found in December 2018. It is , has almost 25 million digits, and to print it out in full at 75 digits per line and 50 lines per page would take many thousands of pages!
Perfect numbers
Another important feature of Mersenne primes is their connection with perfect numbers. We recall from Chapter 1 that a number N is perfect if N is the sum of its proper factors (those that are less than N). For example, you’ve seen that
and that the next two perfect numbers are 496 and 8128. There are then no more of them until 33,550,336.
Is there a formula for perfect numbers? To find out, let’s factorize the ones we already know:
These numbers all have the form , where the number in parentheses is a Mersenne prime.
In Book IX of his Elements, Euclid investigated perfect numbers and found that the number
is indeed perfect whenever is a prime. To see why, let . Then the proper factors of are
What’s the sum of all these factors? Using the fact that
we can write
So we find, after some calculation, that the sum of all the proper factors is
which equals N.
So is perfect.
Are all perfect numbers of this type, or might there be some others? In 1638 the French philosopher René Descartes wrote to Mersenne saying that he believed that all even perfect numbers must indeed be of Euclid’s form, , for some number n, and this was subsequently proved by Euler and published posthumously. Euler also proved that every even perfect number must end with either 6 or 8: for example, the next three perfect numbers are
But what about odd perfect numbers? Descartes conjectured that these cannot exist, and it remains unknown to this day whether he was correct. But if there were any odd perfect numbers, then they would certainly be difficult to find. For a start, it’s known that any odd perfect number must be at least 101500, that it must have at least 101 prime factors with at least ten different ones, and that it must have the form , or , for some integer n. Few mathematicians consider their existence likely.
Fermat primes
Having just looked at prime numbers of the form , let’s now turn our attention to numbers of the form . As we saw in Chapter 1, Pierre de Fermat investigated these numbers (now called Fermat numbers) and found five of them that are prime:
So is it true that is prime when, and only when, n is a power of 2? Let’s draw up another table:
Table 3. Numbers of the form
It certainly seems as though this is the case.
We first show that if is prime, then n must be a power of 2. To do this, w
e note that if n had an odd factor (other than 1), then would be composite. For, if we write , where m is odd, then it can be shown that is a divisor of : for example, if , , and , then
It follows that if is prime, then n can have no odd factor, and so must be a power of 2.
Although Fermat was convinced that if n is a power of 2, then must be prime, he confessed that he was unable to prove this, or even to show that the next one, the ten-digit number
is prime. In desperation, he wrote around to fellow mathematicians challenging them to prove his ‘distinguished theorem’. At the time, no-one could do so.
Euler learned of Fermat’s challenge in 1729, and after much tedious experimentation he showed it to be divisible by 641—in fact,
He later discovered that if had any prime factors, then they would have to be of the form , for some integer k. This limits the search considerably, because the smallest prime numbers of this type are 193, 257, 449, and 557 (none of which divides ), and 641 (which does, as we’ve seen).