Number theory revealed: a masterclass

Contents......Page 10
Preface......Page 18
Gauss’s......Page 24
Notation......Page 26
Prerequisites......Page 28
 0.1. Fibonacci numbers and other recurrence sequences......Page 30
 0.2. Formulas for sums of powers of integers......Page 32
 0.3. The binomial theorem, Pascal’s triangle, and the binomial coefficients......Page 33
Appendices for Preliminary Chapter on Induction......Page 37
 Appendix 0A. A closed formula for sums of powers......Page 38
 Appendix 0B. Generating functions......Page 40
 Appendix 0C. Finding roots of polynomials......Page 44
 Appendix 0D. What is a group?......Page 48
 Appendix 0E. Rings and fields......Page 51
 Appendix 0F. Symmetric polynomials......Page 54
 Appendix 0G. Constructibility......Page 59
Chapter 1. The Euclidean algorithm......Page 62
 Appendix 1A. Reformulating the Euclidean algorithm......Page 74
 Appendix 1B. Computational aspects of the Euclidean algorithm......Page 80
 Appendix 1C. Magic squares......Page 83
 Appendix 1D. The Frobenius postage stamp problem......Page 86
 Appendix 1E. Egyptian fractions......Page 88
Chapter 2. Congruences......Page 90
 Appendix 2A. Congruences in the language of groups......Page 100
 Appendix 2B. The Euclidean algorithm for polynomials......Page 104
Chapter 3. The basic algebra of number theory......Page 110
 Appendix 3A. Factoring binomial coefficients and Pascal’s triangle modulo......Page 128
 Appendix 3B. Solving linear congruences......Page 133
 Appendix 3C. Groups and rings......Page 138
 Appendix 3D. Unique factorization revisited......Page 141
 Appendix 3E. Gauss’s approach......Page 145
 Appendix 3F. Fundamental theorems and factoring polynomials......Page 146
 Appendix 3G. Open problems......Page 152
Chapter 4. Multiplicative functions......Page 156
 Appendix 4A. More multiplicative functions......Page 163
 Appendix 4B. Dirichlet series and multiplicative functions......Page 169
 Appendix 4C. Irreducible polynomials modulo......Page 173
 Appendix 4D. The harmonic sum and the divisor function......Page 176
 Appendix 4E. Cyclotomic polynomials......Page 182
Chapter 5. The distribution of prime numbers......Page 184
 Appendix 5A. Bertrand’s postulate and beyond......Page 200
 Appendix 5B. An important proof of infinitely many primes......Page 211
 Appendix 5C. What should be true about primes?......Page 216
 Appendix 5D. Working with Riemann’s zeta-function......Page 221
 Appendix 5E. Prime patterns: Consequences of the Green-Tao Theorem......Page 227
 Appendix 5F. A panoply of prime proofs......Page 231
 Appendix 5G. Searching for primes and prime formulas......Page 233
 Appendix 5H. Dynamical systems and infinitely many primes......Page 237
Chapter 6. Diophantine problems......Page 244
 Appendix 6A. Polynomial solutions of Diophantine equations......Page 254
 Appendix 6B. No Pythagorean triangle of square area via Euclidean geometry......Page 258
 Appendix 6C. Can a binomial coefficient be a square?......Page 262
Chapter 7. Power residues......Page 264
 Appendix 7A. Card shuffling and Fermat’s Little Theorem......Page 281
 Appendix 7B. Orders and primitive roots......Page 287
 Appendix 7C. Finding......Page 294
 Appendix 7D. Orders for finite groups......Page 298
 Appendix 7E. Constructing finite fields......Page 302
 Appendix 7F. Sophie Germain and Fermat’s Last Theorem......Page 307
 Appendix 7G. Primes of the form......Page 309
 Appendix 7H. Further congruences......Page 313
 Appendix 7I. Primitive prime factors of recurrence sequences......Page 319
Chapter 8. Quadratic residues......Page 324
 Appendix 8A. Eisenstein’s proof of quadratic reciprocity......Page 344
 Appendix 8B. Small quadratic non-residues......Page 348
 Appendix 8C. The first proof of quadratic reciprocity......Page 352
 Appendix 8D. Dirichlet characters and primes in arithmetic progressions......Page 355
 Appendix 8E. Quadratic reciprocity and recurrence sequences......Page 362
Chapter 9. Quadratic equations......Page 366
 Appendix 9A. Proof of the local-global principle for quadratic equations......Page 377
 Appendix 9B. Reformulation of the local-global principle......Page 382
 Appendix 9C. The number of representations......Page 385
 Appendix 9D. Descent and the quadratics......Page 389
Chapter 10. Square roots and factoring......Page 394
 Appendix 10A. Pseudoprime tests using square roots of......Page 405
 Appendix 10B. Factoring with squares......Page 409
 Appendix 10C. Identifying primes of a given size......Page 412
 Appendix 10D. Carmichael numbers......Page 416
 Appendix 10E. Cryptosystems based on discrete logarithms......Page 420
 Appendix 10F. Running times of algorithms......Page 422
 Appendix 10G. The AKS test......Page 424
 Appendix 10H. Factoring algorithms for polynomials......Page 428
Chapter 11 Rational approximations to real numbers......Page 432
 Appendix 11A. Uniform distribution......Page 447
 Appendix 11B. Continued fractions......Page 452
 Appendix 11C. Two-variable quadratic equations......Page 467
 Appendix 11D. Transcendental numbers......Page 468
Chapter 12. Binary quadratic forms......Page 472
 Appendix 12A. Composition rules: Gauss, Dirichlet, and Bhargava......Page 485
 Appendix 12B. The class group......Page 494
 Appendix 12C. Binary quadratic forms of positive discriminant......Page 497
 Appendix 12D. Sums of three squares......Page 500
 Appendix 12E. Sums of four squares......Page 504
 Appendix 12F. Universality......Page 508
 Appendix 12G. Integers represented in Apollonian circle packings......Page 511
Chapter 13. The anatomy of integers......Page 516
 Appendix 13A. Other anatomies......Page 522
 Appendix 13B. DirichletL-functions......Page 526
Chapter 14. Counting integral and rational points on curves, modulo p......Page 530
Appendix 14A. Gauss sums......Page 540
Chapter 15. Combinatorial number theory......Page 544
 Appendix 15A. Summing sets modulo......Page 559
 Appendix 15B. Summing sets of integers......Page 561
Chapter 16. The p-adic numbers......Page 564
Chapter 17. Rational points on elliptic curves......Page 576
 Appendix 17A. General Mordell’s Theorem......Page 590
 Appendix 17B. Pythagorean triangles of area......Page 592
 Appendix 17C. 2-parts of abelian groups......Page 594
 Appendix 17D. Waring’s problem......Page 595
Hints for exercises......Page 598
Recommended further reading......Page 612
Index......Page 614