CONTENTS
1. Divisibility and Other Beginnings = 1
1.1. The Ring of Integers = 1
1.2. The Division Algorithm = 4
1.3. Subsets of Z = 5
1.4. Greatest Common Divisor and Least Common Multiple = 8
1.5. An Alternate Approach of Greatest Common Divisor = 14
1.6. Pythagorean Triplets = 18
Notes = 21
References = 21
2. The Unique Factorization Theorem = 22
2.1. What is the Unique Factorization Theorem? = 22
2.2. The Prime Divisibility Lemma as a Route to the UFT = 25
2.3. The Coprime Divisibility Lemma as a Route to the UFT = 26
2.4. Purely Inductive Proofs of the UFT = 27
2.5. A Purely Noninductive Proof of the UFT = 28
2.6. A New View of G.C.D. and L.C.M. = 31
2.7. Characterizing Subsets of the integers = 32
2.8. Some Implications for the Primes = 34
2.9. Valuations : Another Consequence of the UFT = 37
Notes = 42
References = 45
3. Arithmetic Functions = 47
3.1. The Fundamental Arithmetic Functions = 47
3.2. The Number of Divisors of n = 48
3.3. The Sum of the Divisors of n = 50
3.3A. Odd Perfect Numbers = 53
3.4. Multiplicative Arithmetic Functions = 58
3.5. The M$$\ddot o$$bius Function = 61
3.6. Additive Arithmetic Functions = 70
3.7. The Euler Function = 71
3.7A. A Property of the Number 30 = 78
3.8. Averages of Arithmetic Functions = 81
Notes = 99
References = 102
4. The Ring of Arithmetic Functions (A Do-It-Yourself Chapter) = 105
4.1. Rings of Functions and Convolutions = 105
4.2. Inverses and Units = 107
4.3. Inversion Formulas = 109
4.4. The Natural Valuation in % = 109
4.5. Derivations = 114
4.6. Formal Transforms. Dirichlet Series, and Generating Functions = 119
4.7. Units, Primes, and Unique Factorization = 124
4.8. Removing the Asymmetry = 125
Notes = 127
References = 129
5. Congruences = 131
5.1. Basic Definitions and Properties = 131
5.2. Introduction to Polynomial Congruences = 141
5.3. Linear Congruences = 147
5.3A. Average of the Divisor Function over Arithmetic Progressions = 150
5.4. The Chinese Remainder Theorem and Simultaneous Congruences = 154
5.4A. Simultaneous Congruences for Polynomials in Several Variables = 162
5.5. The General Polynomial Congruence = 169
5.5A. Average of the Euler Function over Polynomial Sequences = 175
5.5B. Average of the Divisor Function over Polynomial Sequences = 181
Notes = 185
References = 187
6. Structure of the Reduced Residue Classes = 189
6.1. Reduced Residue Classes as an Abelian Group = 189
6.1A. Primes of the Form km + 1 = 191
6.1B. Basic Notions Concerning Finite Groups = 193
6.1C. Direct Products in Abelian Groups = 198
6.2. The Structure of R($$2^a$$) = 203
6.3. The Structure of R($$p^a$$). p an Odd Prime = 206
6.4. The General Case of R(m) = 213
6.4A. The Vandiver-Birkhoff Theorem = 217
6.5. Characters of R(m) = 227
6.5A. Primitive Characters = 237
6.6. Power Residues = 239
Notes = 241
References = 243
7. Quadratic Congruences = 246
7.1. The General Quadratic Congruence = 246
7.2. Quadratic Residues = 250
7.3. Gauss' Lemma = 254
7.4. Proof of the Quadratic Reciprocity Law = 257
7.4A. Gauss Sums and the Quadratic Reciprocity Law = 260
7.4B. The Least Positive Nonresidue = 265
7.4C. Application to a Diophantine Equation = 271
7.5. The Jacobi Symbol = 273
7.5A. Inductive Proof of the Reciprocity Law = 278
Notes = 281
References = 283
8. Counting Problems (A Do-It-Yourself Chapter) = 284
8.1. Formulation of the Problems = 284
8.1A. Prime to a Given Integer and in a Given Progression = 287
8.1B. Sum of Integers Each Prime to a Given Integer = 289
8.2. Powerfree Integers = 290
8.2A. Squarefree Integers in Small Intervals = 294
8.3. Powerful Integers = 295
8.4. Power Residues Modulo a Prime = 298
8.5. Primitive Roots of a Prime = 301
8.5A. Squareful Primitive Roots = 306
8.5B. Consecutive Primitive Roots = 308
8.6. Combinatorial Identities = 312
Notes = 314
References = 315
9. The Elements of Prime Number Theory = 317
9.1. Simple Beginnings = 317
9.1A. Indirect Counting = 322
9.2. The Processing of log [x]1 = 327
9.2A. Bounds and Upper and Lower Limits = 336
9.2B. A Lower Bound Property of the Eulcr Function = 339
9.2C. The Number of Prime Factors of an Integer = 341
9.2D. The Smallest Positive Quadratic Nonresidue = 348
9.3. Bertrand's Postulate, the Ideas of Chebychev = 350
9.3A. Proof of Bertrand's Postulate = 357
9.3B. Ramanujan's Idea = 361
9.3C. The Erdos Ideas = 363
9.3D. The Theorem of I Schur = 369
9.4. Primes in Arithmetic Progressions = 374
9.4A. A Chebychev Approach to Primes in Arithmetic Progressions = 386
Notes = 396
References = 398
10. The Prime Number Theorem = 400
10.1 Statements of the Prime Number Theorem = 400
10.2. The Role of the M$$\ddot o$$bius Inversion Formula = 405
10.3. Equivalent Formulations of the Prime Number Theorem = 408
10.4. The Selberg Symmetry Formula = 416
10.5. Immediate Consequences of the Symmetry Formula = 424
10.6. Selberg's Derivation of the Prime Number Theorem = 428
10.7. The Erdos Derivation of the Prime Number Theorem = 439
Notes = 449
References = 451
Index = 453
