Table of Contents
About the Author v
Acknowledgments vii
Introduction xi
1 Euclid's Algorithm 1
1.1 Some Examples of Rings 1
1.2 Euclid's Algorithm 5
1.3 Invertible Elements Modulo n 9
1.4 Solving Linear Congruences 13
1.5 The Chinese Remainder Theorem 16
1.6 Prime Numbers 19
Hints for Some Exercises 26
2 Polynomial Rings 27
2.1 Long Division of Polynomials 28
2.2 Highest Common Factors 34
2.3 Uniqueness of Factorization 38
2.4 Irreducible Polynomials 40
2.5 Unique Factorization Domains 46
Hints for Some Exercises 50
3 Congruences Modulo Prime Numbers 53
3.1 Fermat's Little Theorem 55
3.2 The Euler Totient Function 57
3.3 Cyclotomic Polynomials and Primitive Roots 61
3.4 Public Key Cryptography 68
3.5 Quadratic Reciprocity 73
3.6 Congruences in an Arbitrary Ring 84
3.7 Proof of the Second Nebensatz 91
3.8 Gauss Sums and the Proof of Quadratic Reciprocity 93
Hints for Some Exercises 99
4 p-Adic Methods in Number Theory 101
4.1 Hensel's Lemma 101
4.2 Quadratic Congruences 112
4.3 p-Adic Convergence of Series 116
4.4 p-Adic Logarithms and Exponential Maps 124
4.5 Teichmüller Lifts 130
4.6 The Ring of p-Adic Integers 139
Hints for Some Exercises 148
5 Diophantine Equations and Quadratic Rings 149
5.1 Diophantine Equations and Unique Factorization 149
5.2 Quadratic Rings 152
5.3 Norm-Euclidean Quadratic Rings 159
5.4 Decomposing Primes in Quadratic Rings 167
5.5 Continued Fractions 176
5.6 Pell's Equation 185
5.7 Real Quadratic Rings and Diophantine Equations 193
Hints for Some Exercises 199
Solution to Exercises 201
Bibliography 243
Index 245
