|
1 Introduction and Historical Remarks |
|
|
1 | (6) |
|
|
7 | (52) |
|
|
7 | (3) |
|
2.2 Divisibility, Primes, and Composites |
|
|
10 | (6) |
|
2.3 The Fundamental Theorem of Arithmetic |
|
|
16 | (6) |
|
2.4 Congruences and Modular Arithmetic |
|
|
22 | (17) |
|
2.4.1 Basic Theory of Congruences |
|
|
22 | (1) |
|
2.4.2 The Ring of Integers Mod N |
|
|
23 | (4) |
|
2.4.3 Units and the Euler Phi Function |
|
|
27 | (5) |
|
2.4.4 Fermat's Little Theorem and the Order of an Element |
|
|
32 | (4) |
|
|
36 | (3) |
|
2.5 The Solution of Polynomial Congruences Modulo m |
|
|
39 | (9) |
|
2.5.1 Linear Congruences and the Chinese Remainder Theorem |
|
|
39 | (6) |
|
2.5.2 Higher Degree Congruences |
|
|
45 | (3) |
|
2.6 Quadratic Reciprocity |
|
|
48 | (7) |
|
|
55 | (4) |
|
3 The Infinitude of Primes |
|
|
59 | (84) |
|
3.1 The Infinitude of Primes |
|
|
59 | (33) |
|
3.1.1 Some Direct Proofs and Variations |
|
|
59 | (3) |
|
3.1.2 Some Analytic Proofs and Variations |
|
|
62 | (4) |
|
3.1.3 The Fermat and Mersenne Numbers |
|
|
66 | (5) |
|
3.1.4 The Fibonacci Numbers and the Golden Section |
|
|
71 | (13) |
|
3.1.5 Some Simple Cases of Dirichlet's Theorem |
|
|
84 | (5) |
|
3.1.6 A Topological Proof and a Proof Using Codes |
|
|
89 | (3) |
|
|
92 | (20) |
|
3.2.1 Pythagorean Triples |
|
|
93 | (3) |
|
3.2.2 Fermat's Two-Square Theorem |
|
|
96 | (4) |
|
|
100 | (7) |
|
3.2.4 Lagrange's Four Square Theorem |
|
|
107 | (3) |
|
3.2.5 The Infinitude of Primes Through Continued Fractions |
|
|
110 | (2) |
|
|
112 | (19) |
|
3.4 Twin Prime Conjecture and Related Ideas |
|
|
131 | (1) |
|
3.5 Primes Between x and 2x |
|
|
132 | (1) |
|
3.6 Arithmetic Functions and the Mobius Inversion Formula |
|
|
133 | (5) |
|
|
138 | (5) |
|
|
143 | (76) |
|
4.1 The Prime Number Theorem---Estimates and History |
|
|
143 | (4) |
|
4.2 Chebyshev's Estimate and Some Consequences |
|
|
147 | (12) |
|
4.3 Equivalent Formulations of the Prime Number Theorem |
|
|
159 | (10) |
|
4.4 The Riemann Zeta Function and the Riemann Hypothesis |
|
|
169 | (17) |
|
4.4.1 The Real Zeta Function of Euler |
|
|
170 | (5) |
|
4.4.2 Analytic Functions and Analytic Continuation |
|
|
175 | (4) |
|
4.4.3 The Riemann Zeta Function |
|
|
179 | (7) |
|
4.5 The Prime Number Theorem |
|
|
186 | (7) |
|
|
193 | (5) |
|
|
198 | (8) |
|
4.8 Some Extensions and Comments |
|
|
206 | (7) |
|
|
213 | (6) |
|
5 Primality Testing---An Overview |
|
|
219 | (66) |
|
5.1 Primality Testing and Factorization |
|
|
219 | (1) |
|
|
220 | (16) |
|
5.2.1 Brun's Sieve and Bran's Theorem |
|
|
226 | (10) |
|
5.3 Primality Testing and Prime Records |
|
|
236 | (27) |
|
5.3.1 Pseudo-Primes and Probabilistic Testing |
|
|
241 | (8) |
|
5.3.2 The Lucas--Lehmer Test and Prime Records |
|
|
249 | (6) |
|
5.3.3 Some Additional Primality Tests |
|
|
255 | (2) |
|
5.3.4 Elliptic Curve Methods |
|
|
257 | (6) |
|
5.4 Cryptography and Primes |
|
|
263 | (7) |
|
5.4.1 Some Number Theoretic Cryptosystems |
|
|
267 | (3) |
|
5.5 Public Key Cryptography and the RSA Algorithm |
|
|
270 | (3) |
|
5.6 Elliptic Curve Cryptography |
|
|
273 | (3) |
|
|
276 | (6) |
|
|
282 | (3) |
|
6 Primes and Algebraic Number Theory |
|
|
285 | (86) |
|
6.1 Algebraic Number Theory |
|
|
285 | (2) |
|
6.2 Unique Factorization Domains |
|
|
287 | (21) |
|
6.2.1 Euclidean Domains and the Gaussian Integers |
|
|
293 | (8) |
|
6.2.2 Principal Ideal Domains |
|
|
301 | (3) |
|
6.2.3 Prime and Maximal Ideals |
|
|
304 | (4) |
|
6.3 Algebraic Number Fields |
|
|
308 | (21) |
|
6.3.1 Algebraic Extensions of Q |
|
|
316 | (3) |
|
6.3.2 Algebraic and Transcendental Numbers |
|
|
319 | (2) |
|
6.3.3 Symmetric Polynomials |
|
|
321 | (4) |
|
6.3.4 Discriminant and Norm |
|
|
325 | (4) |
|
|
329 | (19) |
|
6.4.1 The Ring of Algebraic Integers |
|
|
331 | (2) |
|
|
333 | (2) |
|
6.4.3 Quadratic Fields and Quadratic Integers |
|
|
335 | (4) |
|
6.4.4 The Transcendence of e and π |
|
|
339 | (3) |
|
6.4.5 The Geometry of Numbers---Minkowski Theory |
|
|
342 | (3) |
|
6.4.6 Dirichlet's Unit Theorem |
|
|
345 | (3) |
|
|
348 | (18) |
|
6.5.1 Unique Factorization of Ideals |
|
|
350 | (7) |
|
6.5.2 An Application of Unique Factorization |
|
|
357 | (2) |
|
6.5.3 The Ideal Class Group |
|
|
359 | (2) |
|
|
361 | (3) |
|
|
364 | (2) |
|
|
366 | (5) |
|
7 The Fields Qp of p-Adic Numbers: Hensel's Lemma |
|
|
371 | (34) |
|
7.1 The p-Adic Fields and p-Adic Expansions |
|
|
371 | (2) |
|
7.2 The Construction of the Real Numbers |
|
|
373 | (8) |
|
7.2.1 The Completeness of Real Numbers |
|
|
373 | (3) |
|
7.2.2 The Construction of R |
|
|
376 | (5) |
|
7.2.3 The Characterization of R |
|
|
381 | (1) |
|
7.3 Normed Fields and Cauchy Completions |
|
|
381 | (1) |
|
|
382 | (5) |
|
|
385 | (2) |
|
7.5 The Construction of Qp |
|
|
387 | (7) |
|
7.5.1 p-Adic Arithmetic and p-Adic Expansions |
|
|
387 | (7) |
|
|
394 | (4) |
|
7.6.1 Principal Ideals and Unique Factorization |
|
|
396 | (1) |
|
7.6.2 The Completeness of Zp |
|
|
397 | (1) |
|
|
398 | (1) |
|
7.8 Hensel's Lemma and Applications |
|
|
398 | (5) |
|
7.8.1 The Non-isomorphism of the p-Adic Fields |
|
|
402 | (1) |
|
|
403 | (2) |
Bibliography |
|
405 | (4) |
Index |
|
409 | |