Prime numbers are the multiplicative building blocks of natural numbers. Understanding their overall influence and especially their distribution gives rise to central questions in mathematics and physics. In particular, their finer distribution is closely connected with the Riemann hypothesis, the most important unsolved problem in the mathematical world. This book comprehensively covers all the topics met in first courses on multiplicative number theory and the distribution of prime numbers. The text is based on courses taught successfully over many years at the University of Michigan, Imperial College, London and Pennsylvania State University.

if k and ak lie in the same subset, otherwise put ε k = −1. Note that ε k = ε− k. Let π+ be the permutation that leaves N fixed and maps P to itself by the formula k → ε kak (mod n). Let π− be the map that leaves P fixed and maps N to itself by the formula k → ε kak (mod n). Finally let π ∗ be the product of those transpositions ( ak − ak) for which k ∈ P and ak ∈ N . Show that the map x → ax (mod n) is the permutation π ∗π +π −. Let σ be the ‘sign change permutation’ x → − x (mod n).

the last integral by parts (recall Theorem A.2), we find that the right-hand side above is b b f ( x) d x − f ( b){ b} + f ( a){ a} + { x} d f ( x). a a The familiar ‘integral test’ is an immediate corollary of this identity, and indeed the last term on the right gives an explicit representation of the difference between f ( n) and f ( x). If f has a continuous first derivative then (by Theorem A.3) we may replace d f ( x) by f ′( x) d x in the last integral, so that b b f ( n) =

that mp ∈ S. Show that m ≡ 1 (mod p − 1). (c) Let p be given. Show that the number of m such that mp ≤ x and mp ∈ S is ≪ x/ p 2. (d) Show that the number of n ∈ S, n ≤ x, such that n has a prime factor > y is ≪ x/( y log y). (e) Suppose that x/ y < n ≤ x and that n is composed entirely of primes p ≤ y. Show that ω( n) ≥ (log x)/(log y) − 1. (f) By Exercise 4, or otherwise, show that the number of n ≤ x such that ω( n) ≥ z is ≪ x(log x)2/3 z. (g) Conclude that the number of n ≤ x

many n. For a survey of extreme value estimates of arithmetic functions, see Nicolas (1988). Theorem 2.12 is due to Turán (1934), although Corollary 2.13 and the es- timate (2.22) used in the proof of Theorem 2.12 were established earlier by Hardy & Ramanujan (1917). Kubilius (1956) generalized Turán’s inequality to arbitrary additive functions. See Tenenbaum (1995, pp. 302–304) for a proof, and discussion of the sharpest constants. Theorem 2.14 is due to Hall & Tenenbaum (1988, pp. 2,

absolute constant unless the contrary is indicated. For example, if C is liable to depend on a parameter α, we might say, ‘For any fixed value of α, f ( x) = O( g( x))’. Alternatively, we might say, ‘ f ( x) = O( g( x)) where the implicit constant may depend on α’, or more briefly, f ( x) = Oα( g( x)). When there is no main term, instead of writing f ( x) = O( g( x)) we save a pair of parentheses by writing instead f ( x) ≪ g( x). This is read, ‘ f ( x) is less-than-less-than g( x)’, and we