1.7. Notes 27
Elementary Methods in the Analytic Theory of Numbers by A. O. Gel-
fond and Y. V. Linnik is a classic that covers some of the material of this
chapter in greater depth, and other topics as well. Elementary methods in
number theory by M. B. Nathanson and Not Always Buried Deep by P. Pol-
lack also treat elementary techniques in analytic number theory. Material
of this kind may also be found in Introduction to the Theory of Numbers
by G. H. Hardy and E. M. Wright, Lectures on Elementary Number Theory
by Hans Rademacher, and Introduction to the Theory of Numbers by H. N.
1.7. Notes
Gauss never published his empirical investigations on the distribution of the primes,
but these are known from a letter that he wrote on Christmas Eve of 1849 to a
former student of his, the astronomer J. F. F. Encke, and also from cryptic jottings
in his research diary and on a flyleaf of a logarithm table. See pages 444–447 of
volume II and pages 11–18 of volume X of his collected works [Gau33].
Legendre published the prime factorization of the factorial in the 1808 edition
of his treatise Essai sur la Th´ eorie des Nombres [Leg08]. There he also proposed
log(x) 1.08366
as an excellent approximation. Today it is known that li(x) is a much better
approximation for very large x, and that the asymptotically best approximation to
π(x) of the form x/(log(x)−A) is obtained for A = 1. But Legendre’s approximation
is better than Gauss’ approximation in the interval between x =
and x =
4·106, which stretches beyond the range of the tables of primes available in the
early nineteenth century. Gauss makes a comment in his letter to Encke on the
approximation of Legendre, to the effect that he does not care to commit himself
as to what limit A(x) in
π(x) =
log(x) A(x)
may tend to as x +∞.
Legendre made yet a third discovery of great importance to the development of
prime number theory. Since antiquity an algorithm had been known for efficiently
constructing tables of primes. The algorithm is called the Sieve of Eratosthenes,
after the Hellenistic scholar Eratosthenes of Cyrene. We will explain how his al-
gorithm may be used to construct a table of primes up to 30. Start with a list of
the integers n with 2 n 30. Keep the integer 2 but strike out all its proper
multiples. Then keep the next integer 3, but strike out all its proper multiples.
Next keep 5, but strike out all its proper multiples. The integers left in the list are
the primes 2 p 30. For every composite integer n 30 has some prime divisor

30 5.5. Note that we obtain the primes in the interval [6, 30] by remov-
ing from the set of integers in that interval those that lie in the three arithmetic
progressions 2Z, 3Z and 5Z. Legendre reformulated the Sieve of Eratosthenes in
terms of the principle of exclusion and inclusion from combinatorics, potentially
Previous Page Next Page