Gérald Tenenbaum and Michel Mendès France

Preface to the English Edition ix
Preface to the French Edition xi
Notation and conventions xvii
Chapter 1. Genesis: From Euclid to Chebyshev 1
0. Introduction 1
1. Canonical decomposition 4
2. Congruences 5
3. Cryptographic intermezzo: public key systems 8
4. Quadratic residues 11
5. Return to the infinitude of the set of primes 12
6. The sieve of Eratosthenes 14
7. The Chebyshev theorems 16
8. Mertens’ theorems 21
9. Brun’s sieve and the twin prime conjecture 25

Chapter 2. The Riemann Zeta Function 29
0. Introduction 29
vii
viii Contents
1. Euler’s product 30
2. Analytic continuation 32
3. The line s = 1 and the prime number theorem 38
4. The Riemann hypothesis 42
5. Arithmetic consequences of information on the zeros 46

Chapter 3. Stochastic Distribution of Prime Numbers 51
0. Introduction 51
1. Arithmetic progressions 52
2. Cram´er’s model 61
3. Uniform distribution modulo one 67
4. Geometric vision 72

Chapter 4. An Elementary Proof of the Prime Number Theorem 77
0. Introduction 77
1. Integration by parts 80
2. Convolution of arithmetic functions 81
3. The M¨obius function 85
4. The mean value of the M¨obius function and the prime number theorem 88
5. Integers free of large, or small, prime factors 92
6. Dickman’s function 96
7. Daboussi’s proof, revisited 99

Chapter 5. The Major Conjectures 105
Further reading 113