Elements of Number Theory

Cover......Page 1
Preface......Page 3
Contents......Page 5
1 Natural numbers and integers......Page 9
1.1 Natural numbers......Page 10
1.2 Induction......Page 11
1.3 Integers......Page 13
1.4 Division with remainder......Page 15
1.5 Binary notation......Page 16
1.6 Diophantine equations......Page 19
1.7 The Diophantus chord method......Page 22
1.8 Gaussian integers......Page 25
1.9 Discussion......Page 28
2.1 The gcd by subtraction......Page 30
2.2 The gcd by division with remainder......Page 32
2.3 Linear representation of the gcd......Page 34
2.4 Primes and factorization......Page 36
2.5 Consequences of unique prime factorization......Page 38
2.6 Linear Diophantine equations......Page 41
2.7 *The vector Euclidean algorithm......Page 43
2.8 *The map of relatively prime pairs......Page 46
2.9 Discussion......Page 48
3 Congruence arithmetic......Page 51
3.1 Congruence mod n......Page 52
3.2 Congruence classes and their arithmetic......Page 53
3.3 Inverses mod p......Page 56
3.4 Fermat's little theorem......Page 59
3.5 Congruence theorems of Wilson and Lagrange......Page 61
3.6 Inverses mod k......Page 63
3.7 Quadratic Diophantine equations......Page 65
3.8 *Primitive roots......Page 67
3.9 *Existence of primitive roots......Page 70
3.10 Discussion......Page 71
4.1 Trapdoor functions......Page 74
4.2 Ingredients of RSA......Page 77
4.3 Exponentiation mod n......Page 78
4.4 RSA encryption and decryption......Page 80
4.5 Digital signatures......Page 81
4.7 Discussion......Page 82
5 The Pell equation......Page 84
5.1 Side and diagonal numbers......Page 85
5.2 The equation x²—2y² = 1......Page 86
5.3 The group of solutions......Page 88
5.4 The general Pell equation and Z[sqrt(n)]......Page 89
5.5 The pigeonhole argument......Page 92
5.6 *Quadratic forms......Page 95
5.7 *The map of primitive vectors......Page 98
5.8 *Periodicity in the map of x²—ny²......Page 103
5.9 Discussion......Page 107
6 The Gaussian integers......Page 109
6.1 Z[i] and its norm......Page 110
6.2 Divisibility and primes in Z[i] and Z......Page 111
6.3 Conjugates......Page 113
6.4 Division in Z[i]......Page 115
6.5 Fermat's two square theorem......Page 117
6.6 Pythagorean triples......Page 118
6.7 *Primes of the form 4n+1......Page 121
6.8 Discussion......Page 123
7 Quadratic integers......Page 125
7.1 The equation y³ = x²+2......Page 126
7.2 The division property in Z[sqrt(—2)]......Page 127
7.3 The gcd in Z[sqrt(-2)]......Page 129
7.4 Z[sqrt(-3)] and Z[zeta₃]......Page 131
7.5 *Rational solutions of x³+y³ = z³+w³......Page 134
7.6 "The prime sqrt(-3) in Z[zeta₃]......Page 137
7.7 *Fermat's last theorem for n = 3......Page 140
7.8 Discussion......Page 144
8 The four square theorem......Page 146
8.1 Real matrices and C......Page 147
8.2 Complex matrices and H......Page 149
8.3 The quaternion units......Page 151
8.4 Z[i,j,k]......Page 153
8.5 The Hurwitz integers......Page 155
8.6 Conjugates......Page 157
8.7 A prime divisor property......Page 159
8.8 Proof of the four square theorem......Page 160
8.9 Discussion......Page 162
9 Quadratic reciprocity......Page 166
9.1 Primes x²+y², x2+2y², and x²+3y²......Page 167
9.2 Statement of quadratic reciprocity......Page 169
9.3 Euler's criterion......Page 172
9.4 The value of (2/q)......Page 175
9.5 The story so far......Page 177
9.6 The Chinese remainder theorem......Page 179
9.7 The full Chinese remainder theorem......Page 181
9.8 Proof of quadratic reciprocity......Page 183
9.9 Discussion......Page 186
10 Rings......Page 189
10.1 The ring axioms......Page 190
10.2 Rings and fields......Page 192
10.3 Algebraic integers......Page 194
10.4 Quadratic fields and their integers......Page 197
10.5 Norm and units of quadratic fields......Page 200
10.6 Discussion......Page 202
11 Ideals......Page 204
11.1 Ideals and the gcd......Page 205
11.2 Ideals and divisibility in ?......Page 207
11.3 Principal ideal domains......Page 210
11.4 A nonprincipal ideal of Z[sqrt(-3)]......Page 213
11.5 A nonprincipal ideal of Z[sqrt(—5)]......Page 215
11.6 Ideals of imaginary quadratic fields as lattices......Page 217
11.7 Products and prime ideals......Page 219
11.8 Ideal prime factorization......Page 222
11.9 Discussion......Page 225
12 Prime ideals......Page 229
12.1 Ideals and congruence......Page 230
12.2 Prime and maximal ideals......Page 232
12.3 Prime ideals of imaginary quadratic fields......Page 233
12.4 Conjugate ideals......Page 235
12.5 Divisibility and containment......Page 237
12.6 Factorization of ideals......Page 238
12.7 Ideal classes......Page 239
12.8 Primes of the form x²+5y²......Page 241
12.9 Discussion......Page 244
Bibliography......Page 247
Index......Page 253