Number Theory Revealed: an Introduction

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

• CoverTitle pagePrefaceGauss’s Disquisitiones ArithmeticaeNotationThe language of mathematicsPrerequisitesPreliminary Chapter on Induction0.1. Fibonacci numbers and other recurrence sequences0.2. Formulas for sums of powers of integers0.3. The binomial theorem, Pascal’s triangle, and the binomial coefficientsArticles with further thoughts on factorials and binomial coefficientsAdditional exercisesA paper that questions one’s assumptions isChapter 1. The Euclidean algorithm1.1. Finding the gcd1.2. Linear combinations1.3. The set of linear combinations of two integers1.4. The least common multiple1.5. Continued fractions1.6. Tiling a rectangle with squaresAdditional exercisesDivisors in recurrence sequencesAppendix 1A. Reformulating the Euclidean algorithm1.8. Euclid matrices and Euclid’s algorithm1.9. Euclid matrices and ideal transformations1.10. The dynamics of the Euclidean algorithmChapter 2. Congruences2.1. Basic congruences2.2. The trouble with division2.3. Congruences for polynomials2.4. Tests for divisibilityAdditional exercisesBinomial coefficients modulo 𝑝The Fibonacci numbers modulo 𝑑Appendix 2A. Congruences in the language of groups2.6. Further discussion of the basic notion of congruence2.7. Cosets of an additive group2.8. A new family of rings and fields2.9. The order of an elementChapter 3. The basic algebra of number theory3.1. The Fundamental Theorem of Arithmetic3.2. Abstractions3.3. Divisors using factorizations3.4. Irrationality3.5. Dividing in congruences3.6. Linear equations in two unknowns3.7. Congruences to several moduli3.8. Square roots of 1 (mod 𝑛)Additional exercisesReference on the many proofs that √2 is irrationalAppendix 3A. Factoring binomial coefficients and Pascal’s triangle modulo 𝑝3.10. The prime powers dividing a given binomial coefficient3.11. Pascal’s triangle modulo 2References for this chapterChapter 4. Multiplicative functions4.1. Euler’s 𝜙-function4.2. Perfect numbers. “The whole is equal to the sum of its parts.”Additional exercisesAppendix 4A. More multiplicative functions4.4. Summing multiplicative functions4.5. Inclusion-exclusion and the Möbius function4.6. Convolutions and the Möbius inversion formula4.7. The Liouville functionAdditional exercisesChapter 5. The distribution of prime numbers5.1. Proofs that there are infinitely many primes5.2. Distinguishing primes5.3. Primes in certain arithmetic progressions5.4. How many primes are there up to 𝑥?5.5. Bounds on the number of primes5.6. Gaps between primesFurther reading on hot topics in this section5.7. Formulas for primesAdditional exercisesAppendix 5A. Bertrand’s postulate and beyond5.9. Bertrand’s postulate5.10. The theorem of Sylvester and SchurBonus read: A review of prime problems5.11. Prime problemsPrime values of polynomials in one variablePrime values of polynomials in several variablesGoldbach’s conjecture and variantsOther questionsGuides to conjectures and the Green-Tao TheoremChapter 6. Diophantine problems6.1. The Pythagorean equation6.2. No solutions to a Diophantine equation through descentNo solutions through prime divisibilityNo solutions through geometric descent6.3. Fermat’s “infinite descent”6.4. Fermat’s Last TheoremA brief history of equation solvingReferences for this chapterAdditional exercisesAppendix 6A. Polynomial solutions of Diophantine equations6.6. Fermat’s Last Theorem in ℂ[𝕥]6.7. 𝑎 𝑏=𝑐in ℂ[𝕥]Chapter 7. Power residues7.1. Generating the multiplicative group of residues7.2. Fermat’s Little Theorem7.3. Special primes and orders7.4. Further observations7.5. The number of elements of a given order, and primitive roots7.6. Testing for composites, pseudoprimes, and Carmichael numbers7.7. Divisibility tests, again7.8. The decimal expansion of fractions7.9. Primes in arithmetic progressions, revisitedReferences for this chapterAdditional exercisesAppendix 7A. Card shuffling and Fermat’s Little Theorem7.11. Card shuffling and orders modulo 𝑛7.12. The “necklace proof”of Fermat’s Little TheoremMore combinatorics and number theory7.13. Taking powers efficiently7.14. Running time: The desirability of polynomial time algorithmsChapter 8. Quadratic residues8.1. Squares modulo prime 𝑝8.2. The quadratic character of a residue8.3. The residue -18.4. The residue 28.5. The law of quadratic reciprocity8.6. Proof of the law of quadratic reciprocity8.7. The Jacobi symbol8.8. The squares modulo 𝑚Additional exercisesFurther reading on Euclidean proofsAppendix 8A. Eisenstein’s proof of quadratic reciprocity8.10. Eisenstein’s elegant proof, 1844Chapter 9. Quadratic equations9.1. Sums of two squares9.2. The values of 𝑥² 𝑑𝑦²9.3. Is there a solution to a given quadratic equation?9.4. Representation of integers by 𝑎𝑥² 𝑏𝑦²with 𝑥,𝑦rational, and beyond9.5. The failure of the local-global principle for quadratic equations in integers9.6. Primes represented by 𝑥² 5𝑦²Additional exercisesAppendix 9A. Proof of the local-global principle for quadratic equations9.8. Lattices and quotients9.9. A better proof of the local-global principleChapter 10. Square roots and factoring10.1. Square roots modulo 𝑛10.2. Cryptosystems10.3. RSA10.4. Certificates and the complexity classes P and NP10.5. Polynomial time primality testing10.6. Factoring methodsReferences: See [CP05] and [Knu98], as well as:Additional exercisesAppendix 10A. Pseudoprime tests using square roots of 110.8. The difficulty of finding all square roots of 1Chapter 11. Rational approximations to real numbers11.1. The pigeonhole principle11.2. Pell’s equation11.3. Descent on solutions of 𝑥²-𝑑𝑦²=𝑛,𝑑>011.4. Transcendental numbers11.5. The 𝑎𝑏𝑐-conjectureFurther reading for this chapterAdditional exercisesAppendix 11A. Uniform distribution11.7. 𝑛𝛼mod 111.8. Bouncing billiard ballsChapter 12. Binary quadratic forms12.1. Representation of integers by binary quadratic forms12.2. Equivalence classes of binary quadratic forms12.3. Congruence restrictions on the values of a binary quadratic form12.4. Class numbers12.5. Class number oneReferences for this chapterAdditional exercisesAppendix 12A. Composition rules: Gauss, Dirichlet, and Bhargava12.7. Composition and Gauss12.8. Dirichlet composition12.9. Bhargava compositionHints for exercisesRecommended further readingIndexBack 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