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. Shapiro. 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 π(x) ≈ x 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 = 102 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) = 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 eﬃciently 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 p ≤ √ 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

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2014 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.