2.9: The Prime Number Theorem

Last updated
Save as PDF

Page ID: 81409

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$

We have already observed that there are 4 primes less than 10, 25 primes less than 100, and 168 primes less than 1000. And there are 78 498 primes less than 10⁶. So

40% of integers < 10 are prime;

25% of integers < 100 are prime;

16.8% of integers < 1000 are prime; and

7.8498% of integers < 10⁶ are prime.

In other words, the fraction of integers which are prime numbers diminishes as we go up.

The first question to ask is whether prime numbers themselves “run out” at some stage, or whether they go on for ever. The answer is very like that for the counting numbers, or positive integers 1, 2, 3,4, 5,...:

the counting process certainly gets started (with 1); and no matter how far we go, we can always “add 1” to get a larger counting number.

Hence we conclude that the counting numbers “go on for ever”.

Problem 76

(a) (i) Start the process of generating prime numbers by choosing your favorite small prime number and call it p₁.

(ii) Then define $n_{1} = p_{1} + 1$ .

(b) (i) Since $n_{1} > 1$ , n₁ must be divisible by some prime. Explain why p₁ is not a factor of n₁. (What is the remainder when we divide n₁ by p₁?)

(ii) Let p₂ be the smallest prime factor of n₁.

(iii) Define $n_{2} = p_{1} \times p_{2} + 1$

(c) (i) Since n₂ > 1, n₂ must be divisible by some prime. Explain why p₁ and p₂ are not factors of n₂. (What is the remainder when we divide n₁ by p₁, or by p₂?)

(ii) Let p₃ be the smallest prime factor of n₂.

(iii) Define $n_{2} = p_{1} \times p_{2} + 1$

(d) Suppose we have constructed k distinct prime numbers p₁, p₂, p₃, ... , p_k. Explain how we can always construct a prime number p_k+1 different from $p_{1}, p_{2}, \dots, p_{k}$ .

(e) Apply the above process with p₁ = 2 to find p₂, p₃, p₄, p₅.

Once we know that the prime numbers go on for ever, we would like to have a clearer idea as to the frequency with which prime numbers occur among the positive integers. We have already noted that

there are 4 primes between 1 and 10,
and again 4 primes between 10 and 20;
but there is only 1 prime in the 90s;
and then 4 primes between 100 and 110.
And there are no primes at all between 200 and 210.

In other words, the distribution of prime numbers seems to be fairly chaotic. Our understanding of the full picture remains fragmentary, but we are about to see that the apparent chaos in the distribution of prime numbers conceals a remarkable pattern just below the surface.

The next item is only an experiment; but it is a very suggestive experiment. It is artificial, in that what you are invited to count has been carefully chosen to point you in the right direction. The resulting observation is generally referred to as the Prime Number Theorem. The result was conjectured by Legendre (1752–1833) and by Gauss (1777–1855) in the late 1790s – and was proved 100 years later (independently and almost simultaneously) in 1896 by the French mathematician Hadamard (1865–1963) and by the Belgian mathematician de la Vallée Poussin (1866–1962). You will need to access a list of prime numbers up to 5000 say.

Problem 77 Let $π (x)$ denote the number of prime numbers $\leq x$ : so $π (1) = 0$ , $π (2) = 1$ , $π (3) = π (4) = 2$ , $π (100) = 25$ . You are invited to count the number of primes up to certain carefully chosen numbers, and then to study the results. The pattern you should notice works just as well for other numbers – but is considerably harder to spot.

The special values we choose for “x” are

the next integer above successive powers of the special number e,

where e is an important constant in mathematics – an irrational number whose decimal begins 2.7182818 · · ·, and which has its own button on most calculators (see Problem 248).

(a) Complete the following table.

n	eⁿ	next integer N	π(N)
1	2.718⋯	3	2
2	7.389⋯
3	20.08⋯
4	54.59⋯
5	148.41⋯
6	403.42⋯
7	1096.63⋯
8	2980.95⋯
9	8103.08⋯		1019

(b) Find an expression that seems to specify $π (N)$ as a function of n. Hence conjecture an expression for $π (x)$ in terms of x.

Durch planmassiges Tattonieren.

[Through systematic fumbling.]

Carl Friedrich Gauss (1777-1855),

when asked how he came to make so many profound discoveries in mathematics.