“Analytic Number Theory: The
Prime Number Theorem.” Britannica CD, Version 99© 1994-1998. Encyclopædia
Britannica, Inc.
(n) denotes the number of primes in the interval from 1 to n,
Euclid's theorem on the infinitude of primes guarantees that 
(n) 
as n
. It is natural to ask how pn and (n)
grow as functions of n for large n. Irregularities in the
distribution of primes and the lack of a simple formula for determining
primes suggest that precise answers to these questions might be difficult
or impossible to obtain. It seems astonishing to learn that answers can
be obtained, and they are remarkably simple: For large n, the nth
prime pn grows as n log n, whereas (n)
grows as n/log n. Each of these statements implies the other,
and each is known as the prime number theorem. More precisely, the prime
number theorem can be stated in two equivalent forms:
and
These relations are written more simply
as (n) 
n/log
n and pn
n log n and are expressed verbally by saying that (n)
is asymptotic to n/log n and that pn is
asymptotic to n log n, respectively.
The first form was conjectured independently
by Gauss and by Legendre around 1800, but neither provided proof. Gauss
was led to his conjecture by examining a table of primes 
106. He calculated
(n) simply by counting the number of primes in the interval
from 1 to n. This is similar to the exercise done in an earlier
section, in which primes were counted in blocks of 1,000 consecutive integers.
However, if the blocks are not of equal length but are allowed to grow
by a factor of 100, the following values of
(n) and of the ratio n/
(n) are obtained:
The table shows that the ratio n/
(n) grows very slowly compared to n. As the exponents
on the powers of 10 increase by 2, the ratio n /(n)
seems to increase by about 4.6, or 2.3 times the exponent of 10. The exponent
of 10 is the logarithm of n to the base 10, so the table indicates
that n/
(n) grows at about 2.3 times this logarithm. But 2.3 times the
logarithm of a number to base 10 is approximately equal to the natural
logarithm of that number. Comparison of the natural logarithm log n
with the ratio n/ (n)
reveals the following values:
This remarkable agreement between
log n and n/ (n)
suggests that their ratio approaches 1 as n .
Gauss, Legendre, and many other eminent mathematicians of the early 19th
century tried unsuccessfully to prove this conjecture. The first step toward
a proof was made in 1851 by Chebyshev, who showed that if (n)log
n/n has a limit as n ,
then this limit must equal 1.
In 1859 Bernhard Riemann attacked the problem with a new method, using a formula of Euler relating the sum of the reciprocals of the powers of the positive integers with an infinite product extended over the primes. Euler's product formula, devised in 1737, states that, for every real s > 1,
where the product runs through all the primes. Euler derived this formula by writing each factor on the right as an infinite geometric series
with x = pn-s. When all these series are multiplied together and the denominators are arranged in increasing order, the result is the series on the left (because of the fundamental theorem of arithmetic).
Riemann replaced the real variable
s in Euler's product formula with a complex number and showed that
the distribution of prime numbers is intimately related to properties of
the function 
(s)
defined by the series (now called the Riemann zeta function). Riemann
came close to proving the prime number theorem, but not enough was
known during his lifetime about the theory of functions of a complex variable
to complete the proof successfully.
Thirty years later the necessary analytic tools were at hand, and in 1896 Jacques-Salomon Hadamard and Charles Jean de la Vallee-Poussin independently proved the first form of the prime number theorem. The proof was one of the great achievements of analytic number theory. Subsequently, new proofs were discovered, including an elementary proof found in 1949 by Paul Erdos and Atle Selberg that makes no use of complex function theory.
The second form of the prime number theorem is easily deduced from the first form by taking logarithms of both members of equation (1) and then removing a factor log n to obtain
Because log n ,
the factor multiplying log n must tend to zero. The quotient log
log n/log n also tends to zero, hence
This relation, multiplied by equation (1), yields
Now replace n by the nth
prime, pn, in this equation. Then (pn)
= n, and the equation becomes
which implies equation (2). Equation (1) can also be deduced from (2), so the two statements are equivalent.
Each of the following statements involving the Mobius function is also equivalent to the prime number theorem:
The prime number theorem is important
not only because it makes an elegant and simple statement about primes
and has many applications but also because much new mathematics was created
in the attempts to find a proof. This is typical in number theory. Some
problems, very simple to state, are often extremely difficult to solve,
and mathematicians working on these problems often create new areas of
mathematics of independent interest. Another example is the creation of
algebraic number theory as a result of work on the Fermat conjecture.
Famous Problems
and Proofs Main Page