Number theory revealed

Cover......Page 1
Number Theory Revealed:An Introduction......Page 5
Copyright......Page 6
Dedication......Page 7
Epigraph......Page 9
Contents......Page 11
Preface......Page 15
Gauss’s DisquisitionesArithmeticae......Page 21
Notation......Page 23
 The language of mathematics......Page 24
Prerequisites......Page 25
 0.1. Fibonacci numbers and other recurrence sequences......Page 27
 0.2. Formulas for sums of powers of integers......Page 29
 0.3. The binomial theorem, Pascal’s triangle, and the binomial coefficients......Page 30
 Additional exercises......Page 32
 A paper that questions one’s assumptions is......Page 34
 1.1. Finding the gcd......Page 37
 1.2. Linear combinations......Page 39
 1.3. The set of linear combinations of two integers......Page 41
 1.4. The least common multiple......Page 43
 Additional exercises......Page 46
 1.8. Euclid matrices and Euclid’s algorithm......Page 49
 1.9. Euclid matrices and ideal transformations......Page 51
 1.10. The dynamics of the Euclidean algorithm......Page 52
 2.1. Basic congruences......Page 55
 2.2. The trouble with division......Page 58
 2.3. Congruences for polynomials......Page 60
 Additional exercises......Page 61
 Binomial coefficients modulo......Page 62
 The Fibonacci numbers modulo......Page 63
 2.6. Further discussion of the basic notion of congruence......Page 65
 2.7. Cosets of an additive group......Page 66
 2.9. The order of an element......Page 67
 3.1. The Fundamental Theorem of Arithmetic......Page 69
 3.2. Abstractions......Page 71
 3.3. Divisors using factorizations......Page 73
 3.4. Irrationality......Page 75
 3.5. Dividing in congruences......Page 76
 3.6. Linear equations in two unknowns......Page 78
 3.7. Congruences to several moduli......Page 80
 3.8. Square roots of......Page 82
 Additional exercises......Page 84
 is irrational......Page 85
 3.10. The prime powers dividing a given binomial coefficient......Page 87
 3.11. Pascal’s triangle modulo 2......Page 89
 References for this chapter......Page 91
Chapter 4. Multiplicative functions......Page 93
 function......Page 94
 4.2. Perfect numbers.......Page 95
 Additional exercises......Page 97
 4.4. Summing multiplicative functions......Page 100
 4.5. Inclusion-exclusion and the M¨obius function......Page 101
 4.6. Convolutions and the M¨obius inversion formula......Page 102
 4.7. The Liouville function......Page 104
 Additional exercises......Page 105
 5.1. Proofs that there are infinitely many primes......Page 107
 5.2. Distinguishing primes......Page 109
 5.4. How many primes are there up to......Page 112
 Further reading on hot topics in this section......Page 119
 Additional exercises......Page 121
 5.9. Bertrand’s postulate......Page 123
 5.10. The theorem of Sylvester and Schur......Page 124
 Prime values of polynomials in one variable......Page 127
 Prime values of polynomials in several variables......Page 129
 Goldbach’s conjecture and variants......Page 131
 Guides to conjectures and the Green-Tao Theorem......Page 132
 6.1. The Pythagorean equation......Page 135
 No solutions through prime divisibility......Page 138
 6.3. Fermat’s “infinite descent”......Page 140
 6.4. Fermat’s Last Theorem......Page 141
 Additional exercises......Page 143
 6.6. Fermat’s Last Theorem in......Page 145
 in......Page 146
Chapter 7. Power residues......Page 149
 7.1. Generating the multiplicative group of residues......Page 150
 7.2. Fermat’s Little Theorem......Page 151
 7.4. Further observations......Page 154
 7.5. The number of elements of a given order, and primitive roots......Page 155
 7.6. Testing for composites, pseudoprimes, and Carmichael numbers......Page 159
 7.9. Primes in arithmetic progressions, revisited......Page 162
 Additional exercises......Page 163
 7.11. Card shuffling and orders modulo......Page 166
 7.12. The “necklace proof” of Fermat’s Little Theorem......Page 168
 7.13. Taking powers efficiently......Page 169
 7.14. Running time: The desirability of polynomial time algorithms......Page 170
 8.1. Squares modulo prime......Page 173
 8.2. The quadratic character of a residue......Page 175
 8.3. The residue......Page 178
 8.4. The residue......Page 179
 8.5. The law of quadratic reciprocity......Page 181
 8.6. Proof of the law of quadratic reciprocity......Page 183
 Additional exercises......Page 188
 Further reading on Euclidean proofs......Page 191
 8.10. Eisenstein’s elegant proof, 1844......Page 193
 9.1. Sums of two squares......Page 199
 9.2. The values of......Page 202
 9.3. Is there a solution to a given quadratic equation?......Page 203
 rational, and beyond......Page 206
 9.6. Primes represented by......Page 207
 Additional exercises......Page 208
 9.8. Lattices and quotients......Page 210
 9.9. A better proof of the local-global principle......Page 213
 10.1. Square roots modulo......Page 215
 10.2. Cryptosystems......Page 216
 10.3. RSA......Page 218
 10.4. Certificates and the complexity classes......Page 220
 10.5. Polynomial time primality testing......Page 222
 10.6. Factoring methods......Page 223
Appendix 10A. Pseudoprimetests using square roots of 1......Page 226
 11.1. The pigeonhole principle......Page 231
 11.2. Pell’s equation......Page 234
 11.4. Transcendental numbers......Page 239
 Additional exercises......Page 244
 11.7. nα mod 1......Page 246
 11.8. Bouncing billiard balls......Page 248
Chapter 12. Binary quadratic forms......Page 253
 12.1. Representation of integers by binary quadratic forms......Page 254
 12.2. Equivalence classes of binary quadratic forms......Page 256
 12.3. Congruence restrictions on the values of a binary quadratic form......Page 257
 12.4. Class numbers......Page 258
 12.5. Class number one......Page 259
 Additional exercises......Page 262
 12.7. Composition and Gauss......Page 266
 12.8. Dirichlet composition......Page 269
 12.9. Bhargava composition5......Page 271
Hints for exercises......Page 277
Recommended further reading......Page 287
Index......Page 289