Number Theory Revealed: an Introduction

Andrew Granville, University of Montreal, Quebec, Canada, University College London, England, and (formerly) University of Georgia, Athens, GA.

Cover Title page Preface Gauss's Disquisitiones Arithmeticae Notation The language of mathematics Prerequisites Preliminary Chapter on Induction 0.1. Fibonacci numbers and other recurrence sequences 0.2. Formulas for sums of powers of integers 0.3. The binomial theorem, Pascal's triangle, and the binomial coefficients Articles with further thoughts on factorials and binomial coefficients Additional exercises A paper that questions one's assumptions is Chapter 1. The Euclidean algorithm 1.1. Finding the gcd 1.2. Linear combinations 1.3. The set of linear combinations of two integers 1.4. The least common multiple 1.5. Continued fractions 1.6. Tiling a rectangle with squares Additional exercises Divisors in recurrence sequences Appendix 1A. Reformulating the Euclidean algorithm 1.8. Euclid matrices and Euclid's algorithm 1.9. Euclid matrices and ideal transformations 1.10. The dynamics of the Euclidean algorithm Chapter 2. Congruences 2.1. Basic congruences 2.2. The trouble with division 2.3. Congruences for polynomials 2.4. Tests for divisibility Additional exercises Binomial coefficients modulo 𝑝 The Fibonacci numbers modulo 𝑑 Appendix 2A. Congruences in the language of groups 2.6. Further discussion of the basic notion of congruence 2.7. Cosets of an additive group 2.8. A new family of rings and fields 2.9. The order of an element Chapter 3. The basic algebra of number theory 3.1. The Fundamental Theorem of Arithmetic 3.2. Abstractions 3.3. Divisors using factorizations 3.4. Irrationality 3.5. Dividing in congruences 3.6. Linear equations in two unknowns 3.7. Congruences to several moduli 3.8. Square roots of 1 (mod 𝑛) Additional exercises Reference on the many proofs that ?2 is irrational Appendix 3A. Factoring binomial coefficients and Pascal's triangle modulo 𝑝 3.10. The prime powers dividing a given binomial coefficient 3.11. Pascal's triangle modulo 2 References for this chapter Chapter 4. Multiplicative functions 4.1. Euler's 𝜙-function 4.2. Perfect numbers. "The whole is equal to the sum of its parts." Additional exercises Appendix 4A. More multiplicative functions 4.4. Summing multiplicative functions 4.5. Inclusion-exclusion and the Moebius function 4.6. Convolutions and the Moebius inversion formula 4.7. The Liouville function Additional exercises Chapter 5. The distribution of prime numbers 5.1. Proofs that there are infinitely many primes 5.2. Distinguishing primes 5.3. Primes in certain arithmetic progressions 5.4. How many primes are there up to 𝑥? 5.5. Bounds on the number of primes 5.6. Gaps between primes Further reading on hot topics in this section 5.7. Formulas for primes Additional exercises Appendix 5A. Bertrand's postulate and beyond 5.9. Bertrand's postulate 5.10. The theorem of Sylvester and Schur Bonus read: A review of prime problems 5.11. Prime problems Prime values of polynomials in one variable Prime values of polynomials in several variables Goldbach's conjecture and variants Other questions Guides to conjectures and the Green-Tao Theorem Chapter 6. Diophantine problems 6.1. The Pythagorean equation 6.2. No solutions to a Diophantine equation through descent No solutions through prime divisibility No solutions through geometric descent 6.3. Fermat's "infinite descent" 6.4. Fermat's Last Theorem A brief history of equation solving References for this chapter Additional exercises Appendix 6A. Polynomial solutions of Diophantine equations 6.6. Fermat's Last Theorem in ?[𝕥] 6.7. 𝑎 𝑏=𝑐 in ?[𝕥] Chapter 7. Power residues 7.1. Generating the multiplicative group of residues 7.2. Fermat's Little Theorem 7.3. Special primes and orders 7.4. Further observations 7.5. The number of elements of a given order, and primitive roots 7.6. Testing for composites, pseudoprimes, and Carmichael numbers 7.7. Divisibility tests, again 7.8. The decimal expansion of fractions 7.9. Primes in arithmetic progressions, revisited References for this chapter Additional exercises Appendix 7A. Card shuffling and Fermat's Little Theorem 7.11. Card shuffling and orders modulo 𝑛 7.12. The "necklace proof" of Fermat's Little Theorem More combinatorics and number theory 7.13. Taking powers efficiently 7.14. Running time: The desirability of polynomial time algorithms Chapter 8. Quadratic residues 8.1. Squares modulo prime 𝑝 8.2. The quadratic character of a residue 8.3. The residue -1 8.4. The residue 2 8.5. The law of quadratic reciprocity 8.6. Proof of the law of quadratic reciprocity 8.7. The Jacobi symbol 8.8. The squares modulo 𝑚 Additional exercises Further reading on Euclidean proofs Appendix 8A. Eisenstein's proof of quadratic reciprocity 8.10. Eisenstein's elegant proof, 1844 Chapter 9. Quadratic equations 9.1. Sums of two squares 9.2. The values of 𝑥 (2) 𝑑𝑦 (2) 9.3. Is there a solution to a given quadratic equation? 9.4. Representation of integers by 𝑎𝑥 (2) 𝑏𝑦 (2) with 𝑥,𝑦 rational, and beyond 9.5. The failure of the local-global principle for quadratic equations in integers 9.6. Primes represented by 𝑥 (2) 5𝑦 (2) Additional exercises Appendix 9A. Proof of the local-global principle for quadratic equations 9.8. Lattices and quotients 9.9. A better proof of the local-global principle Chapter 10. Square roots and factoring 10.1. Square roots modulo 𝑛 10.2. Cryptosystems 10.3. RSA 10.4. Certificates and the complexity classes P and NP 10.5. Polynomial time primality testing 10.6. Factoring methods References: See [CP05] and [Knu98], as well as: Additional exercises Appendix 10A. Pseudoprime tests using square roots of 1 10.8. The difficulty of finding all square roots of 1 Chapter 11. Rational approximations to real numbers 11.1. The pigeonhole principle 11.2. Pell's equation 11.3. Descent on solutions of 𝑥 (2)-𝑑𝑦 (2)=𝑛,𝑑>0 11.4. Transcendental numbers 11.5. The 𝑎𝑏𝑐-conjecture Further reading for this chapter Additional exercises Appendix 11A. Uniform distribution 11.7. 𝑛𝛼 mod 1 11.8. Bouncing billiard balls Chapter 12. Binary quadratic forms 12.1. Representation of integers by binary quadratic forms 12.2. Equivalence classes of binary quadratic forms 12.3. Congruence restrictions on the values of a binary quadratic form 12.4. Class numbers 12.5. Class number one References for this chapter Additional exercises Appendix 12A. Composition rules: Gauss, Dirichlet, and Bhargava 12.7. Composition and Gauss 12.8. Dirichlet composition 12.9. Bhargava composition Hints for exercises Recommended further reading Index Back Cover

In Number Theory Revealed: An Introduction, Andrew Granville presents a fresh take on the classic structure of a number theory textbook. While it includes the standard topics that one would expect to find in a textbook on elementary number theory, it is also filled throughout with related problems, different approaches to proving key theorems, and interesting digressions that will be of interest even to more advanced readers. At the same time, it assumes relatively little background --- starting, for example, with an introductory chapter on induction --- making it accessible to a wide audience."" - Nathan McNew (Towson University), MAA Reviews ""I strongly recommend the reading of Number Theory Revealed (the 'Masterclass' in particular) not only to all mathematicians but also to anybody scientifically inclined and curious about what mathematics is and how it is done. Not only are the topics well chosen and well presented, but this book is a real page-turner. How often can you say that about a mathematical textbook? Chapeau!"" - Marco Abate, The Mathematical Intelligencer