and so the numbers
are all composite, giving us a string of composite numbers. Another example is:
So, for example, two strings of 1000 successive composite numbers are
and
The prime number theorem
In his inaugural lecture as professor at the University of Bonn in 1975, the distinguished number-theorist Don Zagier remarked:
There are two facts of which I hope to convince you so overwhelmingly that they will permanently be engraved in your hearts.
The first is that the prime numbers belong to the most arbitrary objects studied by mathematicians: they grow like weeds, seeming to obey no other law than that of chance, and nobody can predict where the next one will sprout.
The second fact is even more astonishing, for it states just the opposite: that the prime numbers exhibit stunning regularity, that there are laws governing their behaviour, and that they obey these laws with almost military precision.
To see what he meant by this, we’ll introduce the prime-counting function π(x), which counts the number of primes up to any number x. (This use of the Greek letter π (pi) is nothing to do with the circle number π.) So , because there are exactly four primes (2, 3, 5, and 7) up to 10, and , because there are four more primes (11, 13, 17, and 19). Continuing, we find that , , and .
If we plot the values of the primes up to 100 on a graph we get a jagged pattern—each new prime creates a jump (see Figure 30). But if we stand back and view the primes up to 100,000, we get a lovely smooth curve—the primes do indeed seem to increase very regularly.
30. The distribution of primes.
Table 6. x, π(x), and x /π(x), when x is a power of 10xπ(x)x /π(x)1042.5100254.010001686.010,00012298.1100,000959210.41,000,00078,49812.710,000,000664,57915.0100,000,0005,761,45517.4.........
We can describe this overall regularity more precisely by comparing the values of x and π(x) as x increases. We get the following table which lists x, π(x), and their ratio x/π(x) (to one decimal place).
So up to 100 one-quarter of the numbers are prime, up to 1000 about one-sixth of them are prime, and so on. We can express this ‘thinning-out’ more precisely by noting that whenever x is multiplied by 10, the ratio x/π(x) seems to increase by around 2.3. This number 2.3 turns out to be the natural logarithm of 10. So what do we mean by ‘natural logarithm’?
The logarithm function, introduced in the early 1600s, is a mathematical device for turning multiplication problems into simpler addition ones, by using the basic rule:
There are actually several different logarithm functions, but the one we’re concerned with here is the natural logarithm. It has the property that , where e is an important number that’s about 2.71828. This number appears throughout mathematics and is connected with exponential growth. The graph of the natural logarithm, (sometimes written as ln x), is shown in Figure 31.
31. The graph of the natural logarithm.
Because the natural logarithm x turns multiplication into addition, and, in particular,
we can explain the phenomenon illustrated in the above table of values by saying that, as x increases, π(x) behaves rather like x/log x—or, more precisely, that their ratio approaches 1 as x becomes large. Figure 32 shows the similarity between the graphs of π(x) and x/log x.
32. The graphs of π(x) and x/log x.
Gauss guessed this connection (and even closer approximations) while experimenting with prime numbers at the age of 15. But it wasn’t proved until 1896, when Jacques Hadamard (from France) and Charles de la Vallée Poussin (from Belgium) did so independently, using sophisticated ideas from an area of calculus called complex analysis. It is known as the ‘prime number theorem’.
Prime number theorem: As x increases indefinitely, the ratio of π(x)/(x/log x) tends to 1.
It then took a further fifty years until the Norwegian Atle Selberg and the Hungarian Paul Erdős discovered a purely number-theoretical proof—and because Hadamard lived to 98, de la Vallée Poussin lived to 96, and Selberg lived to 90, it seems that proving the prime number theorem assists longevity!
Primes in arithmetic progressions
In Chapter 3 you met Euclid’s proof that there are infinitely many prime numbers, and we shall now adapt his ideas to derive more precise information. Recalling that every number has the form , , or , we note that numbers of the form 4q and those of the form (other than 2) cannot be prime, because they’re even and so have 2 as a factor. On the other hand, there are many primes of the form and many primes of the form :
primes of the form : 5, 13, 17, 29, 37, 41, 53, 61, 73, 89, 97, 101, …
primes of the form : 3, 7, 11, 19, 23, 31, 43, 47, 59, 67, 71, 79, 83, 103, … .
By modifying Euclid’s argument slightly we can prove that there are infinitely many prime numbers of the form . To do so, we’ll assume (for a contradiction) that there are only finitely many primes, p1, p2, …, pn, of this form (other than 3), but this time we’ll consider the number
which certainly has the form . Now, each of our primes divides the product , and so cannot also divide N. So either N is a new prime of the form , or it’s a composite number, in which case it must split into new primes. But these new primes cannot all be of the form , because multiplying any numbers of that form always gives another one:
So at least one of the new primes must have the
