xii Foreword

particular, big-Oh and little-oh notation), and a first course in modern al-

gebra (covering groups, rings, and fields) should suﬃce for the majority of

the text. A course in complex variables is not required, provided that the

reader is willing to overlook some motivational remarks made in Chapter 7.

Rather than attempt a comprehensive account of elementary methods

in number theory, I have focused on topics that I find particularly attractive

and accessible:

• Chapters 1, 3, 4, and 7 collectively provide an overview of prime

number theory, starting from the infinitude of the primes, mov-

ing through the elementary estimates of Chebyshev and Mertens,

then the theorem of Dirichlet on primes in prescribed arithmetic

progressions, and culminating in an elementary proof of the prime

number theorem.

• Chapter 2 contains a discussion of Gauss’s arithmetic theory of the

roots of unity (cyclotomy), which was first presented in the final

section of his Disquisitiones Arithmeticae. After developing this

theory to the extent required to prove Gauss’s characterization

of constructible regular polygons, we give a cyclotomic proof of

the quadratic reciprocity law, followed by a detailed account of a

little-known cubic reciprocity law due to Jacobi.

• Chapter 5 is a 12-page interlude containing Dress’s proof of the

following result conjectured by Waring in 1770 and established by

Hilbert in 1909: For each fixed integer k ≥ 2, every natural number

can be expressed as the sum of a bounded number of nonnegative

kth powers, where the bound depends only on k.

• Chapter 6 is an introduction to combinatorial sieve methods, which

were introduced by Brun in the early twentieth century. The best-

known consequence of Brun’s method is that if one sums the recip-

rocals of each prime appearing in a twin prime pair p, p + 2, then

the answer is finite. Our treatment of sieve methods is robust

enough to establish not only this and other comparable ‘upper

bound’ results, but also Brun’s deeper “lower bound” results. For

example, we prove that there are infinitely many n for which both

n and n+2 have at most 7 prime factors, counted with multiplicity.

• Chapter 8 summarizes what is known at present about perfect

numbers, numbers which are the sum of their proper divisors.

At the end of each chapter (excepting the interlude) I have included several

nonroutine exercises. Many are based on articles from the mathematical

literature, including both research journals and expository publications like

the American Mathematical Monthly. Here, as throughout the text, I have