Higher arithmetic

0521722365......Page 1
HALF-TITLE......Page 3
TITLE......Page 5
COPYRIGHT......Page 6
CONTENTS......Page 7
INTRODUCTION......Page 10
1. The laws of arithmetic......Page 13
2. Proof by induction......Page 18
3. Prime numbers......Page 20
4. The fundamental theorem of arithmetic......Page 21
5. Consequences of the fundamental theorem......Page 24
6. Euclid’s algorithm......Page 28
7. Another proof of the fundamental theorem......Page 30
8. A property of the H.C.F......Page 31
9. Factorizing a number......Page 34
10. The series of primes......Page 37
Notes......Page 40
1. The congruence notation......Page 43
2. Linear congruences......Page 45
3. Fermat’s theorem......Page 47
4. Euler’s function φ(m)......Page 49
5. Wilson’s theorem......Page 52
6. Algebraic congruences......Page 53
7. Congruences to a prime modulus......Page 54
8. Congruences in several unknowns......Page 57
9. Congruences covering all numbers......Page 58
Notes......Page 59
1. Primitive roots......Page 61
2. Indices......Page 65
3. Quadratic residues......Page 67
4. Gauss’s lemma......Page 70
5. The law of reciprocity......Page 71
6. The distribution of the quadratic residues......Page 75
Notes......Page 78
1. Introduction......Page 80
2. The general continued fraction......Page 82
3. Euler’s rule......Page 84
4. The convergents to a continued fraction......Page 86
5. The equation ax – by = 1......Page 89
6. Infinite continued fractions......Page 90
7. Diophantine approximation......Page 94
8. Quadratic irrationals......Page 95
9. Purely periodic continued fractions......Page 98
10. Lagrange’s theorem......Page 104
11. Pell’s equation......Page 106
12. A geometrical interpretation of continued fractions......Page 111
Notes......Page 113
1. Numbers representable by two squares......Page 115
2. Primes of the form 4k + 1......Page 116
3. Constructions for x and y......Page 120
4. Representation by four squares......Page 123
5. Representation by three squares......Page 126
Notes......Page 127
1. Introduction......Page 128
2. Equivalent forms......Page 129
3. The discriminant......Page 132
4. The representation of a number by a form......Page 134
5. Three examples......Page 136
6. The reduction of positive definite forms......Page 138
7. The reduced forms......Page 140
8. The number of representations......Page 143
9. The class-number......Page 145
Notes......Page 147
1. Introduction......Page 149
2. The equation…......Page 150
3. The equation…......Page 152
4. Elliptic equations and curves......Page 157
5. Elliptic equations modulo primes......Page 163
6. Fermat’s Last Theorem......Page 166
7. The equation…......Page 169
8. Further developments......Page 171
Notes......Page 174
1. Introduction......Page 177
2. Testing for primality......Page 180
3. ‘Random’ number generators......Page 185
4. Pollard’s factoring methods......Page 191
5. Factoring and primality via elliptic curves......Page 197
6. Factoring large numbers......Page 200
7. The Diffie–Hellman cryptographic method......Page 206
8. The RSA cryptographic method......Page 211
9. Primality testing revisited......Page 212
Notes......Page 214
EXERCISES......Page 221
HINTS......Page 234
ANSWERS......Page 237
ENGLISH......Page 247
GERMAN......Page 248
INDEX......Page 249