Chapter 1
The Fundamental Theorem of Arithmetic
1.1 Introduction 13
1.2 Divisibility 14
1.3 Greatest common divisor 14
1.4 Prime numbers 16
1.5 The fundamental theorem of arithmetic 17
1.6 The series of reciprocals of the primes 18
1.7 The Euclidean algorithm 19
1.8 The greatest common divisor of more than two numbers

Chapter 2
Arithmetical Functions and Dirichlet Multiplication
2.1 Introduction 24
2.2 The M6bius function #(n) 24
2.3 The Euler totient function o(n) 25
2.4 A relation connecting o and # 26
2.5 A product formula for o(n) 27
2.6 The Dirichlet product of arithmetical functions 29
2.7 Dirichlet inverses and the M6bius inversion formula 30
2.8 The Mangoldt function A(n) 32
2.9 Multiplicative functions 33
2.10 Multiplicative functions and Dirichlet multiplication 35
2.11 The inverse of a completely multiplicative function 36
2.12 Liouville's function .(n) 37
2.13 The divisor functions a,(n) 38
2.14 Generalized convolutions 39
2.15 Formal power series 41
2.16 The Bell series of an arithmetical function 42
2.17 Bell series and Dirichlet multiplication 44
2.18 Derivatives of arithmetical functions 45
2.19 The Selberg identity 46

Chapter 3
Averages of Arithmetical Functions
3.1 Introduction 52
3.2 The big oh notation. Asymptotic equality of functions 53
3.3 Euler's summation formula 54
3.4 Some elementary asymptotic fi3rmulas 55
3.5 The average order ofd(n) 57
3.6 The average order of the divisor functions a(n) 60
3.7 The average order ore(n) 61
3.8 An application to the distribution of lattice points visible from the origin
3.9 The average order of #(n) and ,of A(n) 64
3.10 The partial sums of a Dirichlet product 65
3.11 Applications to #(n) and A(n) 66
3.12 Another identity for the partial sums of a Dirichlet product 69

Chapter 4
Some Elementary Theorems on the Distribution of Prime Numbers
4.1 Introduction 74
4.2 Chebyshev's functions p(x) and (x) 75
4.3 Relations connecting $(x) and n(x) 76
4.4 Some equivalent forms of the prime number theorem 79
4.5 Inequalities for n(n) and Pn 8.2
4.6 Shapiro'a Tauberian theorem 85
4.7 Applications of Shapiro's theorem 88
4.8 An asymptotic formula for the,. partial sums vx (l/p) 89
4.9 The partial sums of the M/Sbius function 91
4.10 Brief sketch of an elementary proof of the prime number theorem 98
4.11 Selberg's asymptotic formula 99

Chapter 5
Congruences
5.1 Definition and basic properties of congruences 106
5.2 Residue classes and complete residue systems ,109
5.3 Linear congruences 110
5.4 Reduced residue systems and the Euler-Fermat theorem 113
5.5 Polynomial congruences modulo p. Lagrange's theorem 114
5.6 Applications of Lagrange's theorem 115
5.7 Simultaneous linear congruences. The Chinese remainder theorem
5.8 Applications of the Chinese remainder theorem 118
5.9 Polynomial congruences with prime power toodull 120
5.10 The principle of cross-classification 123
5.11 A decomposition property of reduced residue systems

Chapter 6
Finite Abelian Groups and Their Characters
6.1 Definitions 129
6.2 Examples of groups and subgroups 130
6.3 Elementary properties of groups 130
6.4 Construction ofsubgroups 131
6.5 Characters of finite abelJan groups 133
6.6 The character group 135
6.7 The orthogonality relations for characters
6.8 Dirichlet characters !37
6.9 Sums involving Dirichlet characters 140
6.10 The nonvanishing of L(I Z) for real nonprincipal

Chapter 7
Dirichlet's Theorem on Primes in Arithmetic Progressions
7.1 Introduction 146
7.2 Dirichlet's theorem for primes of the form 4n - 1 and 4n + 1
7.3 The plan of the proof of Dirichlet's theorem 148
7.4 Proof of Lemma 7.4 !50
7.5 Proof of Lemma 7.5 151
7.6 Proof of Lemma 7.6 152
7.7 Proof of Lemma 7.8 153
7.8 Proof of Lemma 7.7 153
7.9 Distribution of primes in arithmetic progressions 154

Chapter 8
Periodic Arithmetical Functions and Gauss Sums
8.1 Functions periodic modulo k 157
8.2 Existence of finite Fourier series for periodic arithmetical functions
8.3 Ramanujan's sum and generalizations 160
8.4 Multiplicativeproperties of the sums sk(n) 162
8.5 Gauss sums associated with Dirichlet characters 165
8.6 Dirichlet characters with nonvanishing Gauss sums 166
8.7 Induced moduli and primitive characters 167
8.8 Further properties of induced rnoduli 168
8.9 The conductor of a character 171
8.10 Primitive characters and separable Gauss sums 171
8.11 The finite Fourier series of the Dirichlet characters 172
8.12 P61ya's inequality for the partial sums of primitive characters

Chapter 9
Quadratic Residues and the Quadratic Reciprocity Law
9.1 Quadratic residues 178
9.2 Legendre's symbol and its properties 179
9.3 Evaluation of(-l[p) and (21p) 181
9.4 Gauss'lemma 182
9.5 The quadratic reciprocity law 185
9.6 Applications of the reciprocity law 186
9.7 The Jacobi symbol 187
9.8 Applications to Diophantine equations 190
9.9 Gauss sums and the quadratic reciprocity law 192
9.10 The reciprocity law for quadratic Gauss sums 195
9.11 Another proof of the quadratic reciprocity law 200

Chapter 10
Primitive Roots
10.1 The exponent of a number mod m. Primitive roots 204
10.2 Primitive roots and reduced residue systems 205
10.3 The nonexistence of primitive roots mod 2  for  _ 3 206
10.4 The existence of primitive roots mod p for odd primes p 206
10.5 Primitive roots and quadratic residues 208
10.6 The existence of primitive roo:ts mod p 208
10.7 The existence of primitive roots mod 2p  210
10.8 The nonexistence of primitive roots in the remaining cases 211
10.9 The number of primitive roots mod m 212
10.10 The index calculus 213
10.11 Primitive roots and Dirichlet characters 218
10.12 Real-valued Dirichlet characters mod p 220
10.13 Primitive Dirichlet characters mod p 221

Chapter 11
Dirichlet Series and Euler Products
11.1 Introduction 224
11.2 The half-plane of absolute convergence of a Dirichlet series
11.3 The function defined by a Dirichlet series 226
11.4 Multiplication of Dirichlet series 228
11.5 Euler products 230
11.6 The half-plane of convergence of a Dirichlet series 232
11.7 Analytic properties of Dirichlet series 234
11.8 Dirichlet series with nonnegative coefficients 236
11.9 Dirichlet series expressed as exponentials of Dirichlet series
11.10 Mean value formulas for Dirichlet series 240
11.11 An integral formula for the coefficients of a Dirichlet series
11.12 An integral formula for the partial sums of a Dirichlet series

Chapter 12
The Functions si(x) and L(s, x)
12.1 Introduction 249
12.2 Properties of the gamma function 250
12.3 Integral representation for the Hurwitz zeta function 251
12.4 A contour integral representation for the Hurwitz zeta function 253
12.5 The analytic continuation of the Hurwitz zeta function 254
12.6 Analytic continuation of (s) and L(s, X) 255
12.7 Hurwitz's formula for (s, a) 256
12.8 The functional equation for the Riemann zeta function 259
12.9 A functional equation for the Hurwitz zeta function 261
12.10 The functional equation for L-functions 261
12.11 Evaluation of(-n, a) 264
12.12 Properties of Bernoulli numbers and Bernoulli polynomials 265
12.13 Formulas for L(0, g) 268
12.14 Approximation of (s, a) by finite sums 268
12.15 Inequalities for [(s, a)l 270
12.16 Inequalities for I(s)l and IL(s, g)l 272

Chapter 13
Analytic Proof of the Prime Number Theorem
13.1 The plan of the proof 278
13.2 Lemmas 279
13.3 A contour integral representation for b(x)/x 2 283
13.4 Upper bounds for I(s)l and [('(s)l near the line a = 1 284
13.5 The nonvanishing of (s) on the line a = 1 286
13.6 Inequalities for I1/(s)l and IG'(s)/(s)l 287
13.7 Completion of the proof of the prime number theorem 289
13.8 Zero-free regions for ((s) 291
13.9 The Riemann hypothesis 293
13.10 Application to the divisor function 294
13.11 Application to Euler's totient 297
13.12 Extension of P61ya's inequality for character sums 299

Chapter 14
Partitions
14.1 Introduction 304
14.2 Geometric representation of partitions 307
14.3 Generating functions for partitions 308
14.4 Euler's pentagonal-number theorem 311
14.5 Combinatorial proof of Euler's pentagonal-number theorem
14.6 Euler's recursion formula for n) 315
14.7 An upper bound for p(n) 316
14.8 Jacobi's triple product identity 318
14.9 Consequences of Jacobi's identity 321
14.10 Logarithmic differentiation of generating functions 322
14.11 The partition identities of Ramanujan 324