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