|
1 Introduction: Solving the General Quadratic Congruence Modulo a Prime |
|
|
1 | (8) |
|
1.1 Linear and Quadratic Congruences |
|
|
1 | (4) |
|
1.2 The Disquisitiones Arithmeticae |
|
|
5 | (1) |
|
1.3 Notation, Terminology, and Some Useful Elementary Number Theory |
|
|
6 | (3) |
|
|
9 | (12) |
|
2.1 The Legendre Symbol, Euler's Criterion, and Other Important Things |
|
|
9 | (4) |
|
2.2 The Basic Problem and the Fundamental Problem for a Prime |
|
|
13 | (3) |
|
2.3 Gauss' Lemma and the Fundamental Problem for the Prime 2 |
|
|
16 | (5) |
|
3 Gauss' Theorema Aureum: The Law of Quadratic Reciprocity |
|
|
21 | (58) |
|
3.1 What is a Reciprocity Law? |
|
|
22 | (3) |
|
3.2 The Law of Quadratic Reciprocity |
|
|
25 | (3) |
|
|
28 | (5) |
|
3.4 Proofs of the Law of Quadratic Reciprocity |
|
|
33 | (1) |
|
3.5 A Proof of Quadratic Reciprocity via Gauss' Lemma |
|
|
34 | (4) |
|
3.6 Another Proof of Quadratic Reciprocity via Gauss' Lemma |
|
|
38 | (2) |
|
3.7 A Proof of Quadratic Reciprocity via Gauss Sums: Introduction |
|
|
40 | (1) |
|
3.8 Algebraic Number Theory |
|
|
41 | (8) |
|
3.9 Proof of Quadratic Reciprocity via Gauss Sums: Conclusion |
|
|
49 | (6) |
|
3.10 A Proof of Quadratic Reciprocity via Ideal Theory: Introduction |
|
|
55 | (1) |
|
3.11 The Structure of Ideals in a Quadratic Number Field |
|
|
56 | (8) |
|
3.12 Proof of Quadratic Reciprocity via Ideal Theory: Conclusion |
|
|
64 | (8) |
|
3.13 A Proof of Quadratic Reciprocity via Galois Theory |
|
|
72 | (7) |
|
4 Four Interesting Applications of Quadratic Reciprocity |
|
|
79 | (40) |
|
4.1 Solution of the Fundamental Problem for Odd Primes |
|
|
80 | (3) |
|
4.2 Solution of the Basic Problem |
|
|
83 | (5) |
|
4.3 Sets of Integers Which Are Quadratic Residues of Infinitely Many Primes |
|
|
88 | (3) |
|
4.4 Intermezzo: Dirichlet's Theorem on Primes in Arithmetic Progression |
|
|
91 | (6) |
|
4.5 The Asymptotic Density of Primes |
|
|
97 | (1) |
|
4.6 The Density of Primes Which Have a Given Finite Set of Quadratic Residues |
|
|
98 | (9) |
|
4.7 Zero-Knowledge Proofs and Quadratic Residues |
|
|
107 | (3) |
|
|
110 | (3) |
|
4.9 An Algorithm for Fast Computation of Legendre Symbols |
|
|
113 | (6) |
|
5 The Zeta Function of an Algebraic Number Field and Some Applications |
|
|
119 | (32) |
|
5.1 Dedekind's Ideal Distribution Theorem |
|
|
120 | (9) |
|
5.2 The Zeta Function of an Algebraic Number Field |
|
|
129 | (8) |
|
5.3 The Zeta Function of a Quadratic Number Field |
|
|
137 | (2) |
|
5.4 Proof of Theorem 4.12 and Related Results |
|
|
139 | (7) |
|
5.5 Proof of the Fundamental Theorem of Ideal Theory |
|
|
146 | (5) |
|
|
151 | (10) |
|
6.1 Whither Elementary Proofs in Number Theory? |
|
|
151 | (1) |
|
6.2 An Elementary Proof of Theorem 5.13 |
|
|
152 | (6) |
|
6.3 An Elementary Proof of Theorem 4.12 |
|
|
158 | (3) |
|
7 Dirichlet L-Functions and the Distribution of Quadratic Residues |
|
|
161 | (42) |
|
7.1 Positivity of Sums of Values of a Legendre Symbol |
|
|
162 | (3) |
|
7.2 Proof of Theorem 7.1: Outline of the Argument |
|
|
165 | (1) |
|
7.3 Some Useful Facts About Dirichlet L-Functions |
|
|
166 | (3) |
|
7.4 Calculation of a Gauss Sum |
|
|
169 | (4) |
|
7.5 Some Useful Facts About Analytic Functions of a Complex Variable |
|
|
173 | (3) |
|
7.6 The Convergence of Fourier Series |
|
|
176 | (6) |
|
7.7 Proof of Theorems 7.2, 7.3, and 7.4 |
|
|
182 | (10) |
|
7.8 An Elegant Proof of Lemma 4.8 for Real Dirichlet Characters |
|
|
192 | (4) |
|
7.9 A Proof of Quadratic Reciprocity via Finite Fourier Series |
|
|
196 | (7) |
|
8 Dirichlet's Class-Number Formula |
|
|
203 | (24) |
|
8.1 Some Structure Theory for Dirichlet Characters |
|
|
204 | (1) |
|
8.2 The Structure of Real Primitive Dirichlet Characters |
|
|
205 | (3) |
|
8.3 Elements of the Theory of Quadratic Forms |
|
|
208 | (1) |
|
8.4 Representation of Integers by Quadratic Forms and the Class Number |
|
|
209 | (3) |
|
8.5 The Class-Number Formula |
|
|
212 | (8) |
|
8.6 The Class-Number Formula and the Class Number of Quadratic Fields |
|
|
220 | (3) |
|
8.7 A Character-Theoretic Proof of Quadratic Reciprocity |
|
|
223 | (4) |
|
9 Quadratic Residues and Non-Residues in Arithmetic Progression |
|
|
227 | (46) |
|
9.1 Long Sets of Consecutive Residues and Non-Residues |
|
|
228 | (2) |
|
9.2 Long Sets of Residues and Non-Residues in Arithmetic Progression |
|
|
230 | (2) |
|
9.3 Weil Sums and Their Estimation |
|
|
232 | (6) |
|
9.4 Solution of Problems 1 and 3 |
|
|
238 | (4) |
|
9.5 Solution of Problems 2 and 4: Introduction |
|
|
242 | (2) |
|
9.6 Preliminary Estimate of qε(p) |
|
|
244 | (3) |
|
9.7 Calculation of Σ4(p): Preliminaries |
|
|
247 | (2) |
|
9.8 The (B, S)-Signature of a Prime |
|
|
249 | (2) |
|
9.9 Calculation of Σ4(p): Conclusion |
|
|
251 | (3) |
|
9.10 Solution of Problems 2 and 4: Conclusion |
|
|
254 | (4) |
|
9.11 An Interesting Class of Examples |
|
|
258 | (11) |
|
9.12 The Asymptotic Density of Π+(a, b) |
|
|
269 | (4) |
|
10 Are Quadratic Residues Randomly Distributed? |
|
|
273 | (12) |
|
10.1 Irregularity of the Distribution of Quadratic Residues |
|
|
273 | (2) |
|
10.2 Detecting Random Behavior Using the Central Limit Theorem |
|
|
275 | (2) |
|
10.3 Verifying Random Behavior via a Result of Davenport and Erdos |
|
|
277 | (8) |
Bibliography |
|
285 | (4) |
Index |
|
289 | |