Softcover ISBN:  9781470463700 
Product Code:  MBK/127.S 
List Price:  $99.00 
MAA Member Price:  $89.10 
AMS Member Price:  $79.20 
eBook ISBN:  9781470454241 
Product Code:  MBK/127.E 
List Price:  $89.00 
MAA Member Price:  $80.10 
AMS Member Price:  $71.20 
Softcover ISBN:  9781470463700 
eBook: ISBN:  9781470454241 
Product Code:  MBK/127.S.B 
List Price:  $188.00 $143.50 
MAA Member Price:  $169.20 $129.15 
AMS Member Price:  $150.40 $114.80 
Softcover ISBN:  9781470463700 
Product Code:  MBK/127.S 
List Price:  $99.00 
MAA Member Price:  $89.10 
AMS Member Price:  $79.20 
eBook ISBN:  9781470454241 
Product Code:  MBK/127.E 
List Price:  $89.00 
MAA Member Price:  $80.10 
AMS Member Price:  $71.20 
Softcover ISBN:  9781470463700 
eBook ISBN:  9781470454241 
Product Code:  MBK/127.S.B 
List Price:  $188.00 $143.50 
MAA Member Price:  $169.20 $129.15 
AMS Member Price:  $150.40 $114.80 

Book Details2019; 587 ppMSC: Primary 11
Number Theory Revealed: A Masterclass presents a fresh take on congruences, power residues, quadratic residues, primes, and Diophantine equations and presents hot topics like cryptography, factoring, and primality testing. Students are also introduced to beautiful enlightening questions like the structure of Pascal's triangle mod p, Fermat's Last Theorem for polynomials, and modern twists on traditional questions.
This Masterclass edition contains many additional chapters and appendices not found in Number Theory Revealed: An Introduction. It is ideal for instructors who wish to tailor a class to their own interests and gives wellprepared students further opportunities to challenge themselves and push beyond core number theory concepts, serving as a springboard to many current themes in mathematics. Additional topics in A Masterclass include the curvature of circles in a tiling of a circle by circles, the latest discoveries on gaps between primes, magic squares of primes, a new proof of Mordell's Theorem for congruent elliptic curves, as well as links with algebra, analysis, cryptography, and dynamics.
This book is part of Number Theory Revealed: The Series. Find full tables of contents, sample problems, hints, and appendices, as well as updates about forthcoming related volumes here.
About the Author:
Andrew Granville is the Canada Research Chair in Number Theory at the University of Montreal and professor of mathematics at University College London. He has won several international writing prizes for exposition in mathematics, including the 2008 Chauvenet Prize and the 2019 HalmosFord Prize, and is the author of Prime Suspects (Princeton University Press, 2019), a beautifully illustrated graphic novel murder mystery that explores surprising connections between the anatomies of integers and of permutations.
ReadershipUndergraduate and graduate students interested in introductory number theory.

Table of Contents

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

0A. A closed formula for sums of powers

0.5. Formulas for sums of powers of integers, II

0B. Generating functions

0.6. Formulas for sums of powers of integers, III

0.7. The power series view on the Fibonacci numbers

0C. Finding roots of polynomials

0.8. Solving the general cubic

0.9. Solving the general quartic

0.10. Surds

References discussing solvability of polynomials

0D. What is a group?

0.11. Examples and definitions

0.12. Matrices usually don’t commute

0E. Rings and fields

0.13. Mixing addition and multiplication together: Rings and fields

0.14. Algebraic numbers, integers, and units, I

0F. Symmetric polynomials

0.15. The theory of symmetric polynomials

0.16. Some special symmetric polynomials

0.17. Algebraic numbers, integers, and units, II

0G. Constructibility

0.18. Constructible using only compass and ruler

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

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

1B. Computational aspects of the Euclidean algorithm

1.11. Speeding up the Euclidean algorithm

1.12. Euclid’s algorithm works in “polynomial time”

1C. Magic squares

1.13. Turtle power

1.14. Latin squares

1.15. Factoring magic squares

Reference for this appendix

1D. The Frobenius postage stamp problem

1.16. The Frobenius postage stamp problem, I

1E. Egyptian fractions

1.17. Simple fractions

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 𝑑

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

2B. The Euclidean algorithm for polynomials

2.10. The Euclidean algorithm in ℂ[𝕩]

2.11. Common factors over rings: Resultants and discriminants

2.12. Euclidean domains

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

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

3B. Solving linear congruences

3.12. Composite moduli

3.13. Solving linear congruences with several unknowns

3.14. The Chinese Remainder Theorem in general

When the moduli are not coprime

3C. Groups and rings

3.15. A direct sum

3.16. The structure of finite abelian groups

3D. Unique factorization revisited

3.17. The Fundamental Theorem of Arithmetic, clarified

3.18. When unique factorization fails

3.19. Defining ideals and factoring

3.20. Bases for ideals in quadratic fields

3E. Gauss’s approach

3.21. Gauss’s approach to Euclid’s Lemma

3F. Fundamental theorems and factoring polynomials

3.22. The number of distinct roots of polynomials

The Euclidean algorithm for polynomials

Unique factorization of polynomials modulo 𝑝

3.23. Interpreting resultants and discriminants

3.24. Other approaches to resultants and gcds

Additional exercises

3G. Open problems

3.25. The Frobenius postage stamp problem, II

3.26. Egyptian fractions for 3/𝑏

3.27. The 3𝑥+1 conjecture

Further reading on these open problems

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

4A. More multiplicative functions

4.4. Summing multiplicative functions

4.5. Inclusionexclusion and the Möbius function

4.6. Convolutions and the Möbius inversion formula

4.7. The Liouville function

Additional exercises

4B. Dirichlet series and multiplicative functions

4.9. Dirichlet series

4.10. Multiplication of Dirichlet series

4.11. Other Dirichlet series of interest

4C. Irreducible polynomials modulo 𝑝

4.12. Irreducible polynomials modulo 𝑝

4D. The harmonic sum and the divisor function

4.13. The average number of divisors

4.14. The harmonic sum

4.15. Dirichlet’s hyperbola trick

4E. Cyclotomic polynomials

4.16. Cyclotomic polynomials

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

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 GreenTao Theorem

5B. An important proof of infinitely many primes

5.12. Euler’s proof of the infinitude of primes

Reference on Euler’s many contributions

5.13. The sieve of Eratosthenes and estimates for the primes up to 𝑥

5.14. Riemann’s plan for Gauss’s prediction, I

5C. What should be true about primes?

5.15. The GaussCramér model for the primes

Short intervals

Twin primes

5D. Working with Riemann’s zetafunction

5.16. Riemann’s plan for Gauss’s prediction

5.17. Understanding the zeros

An elementary proof

5.18. Reformulations of the Riemann Hypothesis

Primes and complex analysis

5E. Prime patterns: Consequences of the GreenTao Theorem

5.19. Generalized arithmetic progressions of primes

Consecutive prime values of a polynomial

Magic squares of primes

Primes as averages

5F. A panoply of prime proofs

Furstenberg’s (pointset) topological proof

An analytic proof

A proof by irrationality

5G. Searching for primes and prime formulas

5.21. Searching for prime formulas

5.22. Conway’s prime producing machine

5.23. Ulam’s spiral

5.24. Mills’s formula

Further reading on primes in surprising places

5H. Dynamical systems and infinitely many primes

5.25. A simpler formulation

5.26. Different starting points

5.27. Dynamical systems and the infinitude of primes

5.28. Polynomial maps for which 0 is strictly preperiodic

References for this chapter

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

6A. Polynomial solutions of Diophantine equations

6.6. Fermat’s Last Theorem in ℂ[𝕥]

6.7. 𝑎+𝑏=𝑐 in ℂ[𝕥]

6B. No Pythagorean triangle of square area via Euclidean geometry

An algebraic proof, by descent

6.8. A geometric viewpoint

6C. Can a binomial coefficient be a square?

6.9. Small 𝑘

6.10. Larger 𝑘

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

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

7B. Orders and primitive roots

7.15. Constructing primitive roots modulo 𝑝

7.16. Indices / Discrete Logarithms

7.17. Primitive roots modulo prime powers

7.18. Orders modulo composites

7C. Finding 𝑛th roots modulo prime powers

7.19. 𝑛th roots modulo 𝑝

7.20. Lifting solutions

7.21. Finding 𝑛th roots quickly

7D. Orders for finite groups

7.22. Cosets of general groups

7.23. Lagrange and Wilson

7.24. Normal subgroups

7E. Constructing finite fields

7.25. Classification of finite fields

Further reading on arithmetic associated with finite fields

7.26. The product of linear forms in 𝔽_{𝕢}

7F. Sophie Germain and Fermat’s Last Theorem

7.27. Fermat’s Last Theorem and Sophie Germain

7G. Primes of the form 2ⁿ+𝑘

7.28. Covering sets of congruences

7.29. Covering systems for the Fibonacci numbers

A Fibonacci covering system

7.30. The theory of covering systems

Interesting articles on covering systems

7H. Further congruences

7.31. Fermat quotients

Binomial coefficients

Bernoulli numbers modulo 𝑝

Sums of powers of integers modulo 𝑝²

The Wilson quotient

Beyond Fermat’s Little Theorem

Reference for this section

7.32. Frequency of 𝑝divisibility

Fermat quotients

Bernoulli numbers

7I. Primitive prime factors of recurrence sequences

7.33. Primitive prime factors

Prime power divisibility of secondorder linear recurrence sequences

7.34. Closed form identities and sums of powers

7.35. Primitive prime factors and secondorder linear recurrence sequences

References for this chapter

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

8A. Eisenstein’s proof of quadratic reciprocity

8.10. Eisenstein’s elegant proof, 1844

8B. Small quadratic nonresidues

8.11. The least quadratic nonresidue modulo 𝑝

8.12. The smallest prime 𝑞 for which 𝑝 is a quadratic nonresidue modulo 𝑞

8.13. Character sums and the least quadratic nonresidue

8C. The first proof of quadratic reciprocity

8.14. Gauss’s original proof of the law of quadratic reciprocity

8D. Dirichlet characters and primes in arithmetic progressions

8.15. The Legendre symbol and a certain quotient group

8.16. Dirichlet characters

8.17. Dirichlet series and primes in arithmetic progressions

Uniformity questions

8E. Quadratic reciprocity and recurrence sequences

8.18. The Fibonacci numbers modulo 𝑝

8.19. General secondorder linear recurrence sequences modulo 𝑝

8.20. Prime values in recurrence sequences

Chapter 9. Quadratic equations

9.1. Sums of two squares

9.2. The values of 𝑥²+𝑑𝑦²

9.3. Is there a solution to a given quadratic equation?

9.4. Representation of integers by 𝑎𝑥²+𝑏𝑦² with 𝑥,𝑦 rational, and beyond

9.5. The failure of the localglobal principle for quadratic equations in integers

9.6. Primes represented by 𝑥²+5𝑦²

Additional exercises

9A. Proof of the localglobal principle for quadratic equations

9.8. Lattices and quotients

9.9. A better proof of the localglobal principle

9B. Reformulation of the localglobal principle

9.10. The Hilbert symbol

9.11. The HasseMinkowski principle

This is all discussed in detail in Part I of the wonderful book

9C. The number of representations

9.12. Distinct representations as sums of two squares

9D. Descent and the quadratics

9.13. Further solutions through linear algebra

9.14. The Markov equation

9.15. Apollonian circle packing

Further reading on Apollonian packings

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

10A. Pseudoprime tests using square roots of 1

10.8. The difficulty of finding all square roots of 1

10B. Factoring with squares

Random squares

Euler’s sum of squares method

The Continued fractions method

10.9. Factoring with polynomial values

The large prime variation

10C. Identifying primes of a given size

10.10. The ProthPocklingtonLehmer primality test

Secondorder linear recurrences

References for this chapter

10D. Carmichael numbers

10.11. Constructing Carmichael numbers

10.12. Erdős’s construction

The computational evidence

References for this chapter

10E. Cryptosystems based on discrete logarithms

10.13. The DiffieHellman key exchange

10.14. The El Gamal cryptosystem

10F. Running times of algorithms

10.15. P and NP

10.16. Difficult problems

10G. The AKS test

10.17. A computationally quicker characterization of the primes

10.18. A set of extraordinary congruences

Upper bounds on 𝐺

Lower bounds on 𝐺

References for this chapter

10H. Factoring algorithms for polynomials

10.19. Testing polynomials for irreducibility

10.20. Testing whether a polynomial is squarefree

10.21. Factoring a squarefree polynomial modulo 𝑝

References for this chapter

Chapter 11. Rational approximations to real numbers

11.1. The pigeonhole principle

11.2. Pell’s equation

11.3. Descent on solutions of 𝑥²𝑑𝑦²=𝑛,𝑑>0

11.4. Transcendental numbers

11.5. The 𝑎𝑏𝑐conjecture

Further reading for this chapter

Additional exercises

11A. Uniform distribution

11.7. 𝑛𝛼 mod 1

11.8. Bouncing billiard balls

11B. Continued fractions

11.9. Continued fractions for real numbers

11.10. How good are these approximations?

11.11. Periodic continued fractions and Pell’s equation

11.12. Quadratic irrationals and periodic continued fractions

11.13. Solutions to Pell’s equation from a wellselected continued fraction

11.14. Sums of two squares from continued fractions

Modern uses of continued fractions

11C. Twovariable quadratic equations

11.15. Integer solutions to 2variable quadratics

11D. Transcendental numbers

11.16. Diagonalization

11.17. The hunt for transcendental numbers

11.18. Normal numbers

Normal digits of numbers

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

12A. Composition rules: Gauss, Dirichlet, and Bhargava

12.7. Composition and Gauss

12.8. Dirichlet composition

12.9. Bhargava composition

12B. The class group

12.10. A dictionary between binary quadratic forms and ideals

12.11. Elements of order two in the class group

References for this chapter

12C. Binary quadratic forms of positive discriminant

12.12. Binary quadratic forms with positive discriminant, and continued fractions

12.13. The set of automorphisms

12D. Sums of three squares

12.14. Connection between sums of 3 squares and ℎ(𝑑)

12.15. Dirichlet’s class number formula

12E. Sums of four squares

12.16. Sums of four squares

12.17. Quaternions

12.18. The number of representations

12F. Universality

12.19. Universality of quadratic forms

References for this appendix

12G. Integers represented in Apollonian circle packings

12.20. Combining these linear transformations

Further reading on Apollonian packings

Chapter 13. The anatomy of integers

13.1. Rough estimates for the number of integers with a fixed number of prime factors

13.2. The number of prime factors of a typical integer

13.3. The multiplication table problem

13.4. Hardy and Ramanujan’s inequality

13A. Other anatomies

13.5. The anatomy of polynomials in finite fields

13.6. The anatomy of permutations

More on mathematical anatomies

13B. Dirichlet 𝐿functions

13.7. Dirichlet series

Further exercises

Chapter 14. Counting integral and rational points on curves, modulo 𝑝

14.1. Diagonal quadratics

14.2. Counting solutions to a quadratic equation and another proof of quadratic reciprocity

14.3. Cubic equations modulo 𝑝

14.4. The equation 𝐸_{𝑏}:𝑦²=𝑥³+𝑏

14.5. The equation 𝑦²=𝑥³+𝑎𝑥

14.6. A more general viewpoint on counting solutions modulo 𝑝

14A. Gauss sums

14.7. Identities for Gauss sums

14.8. Dirichlet 𝐿functions at 𝑠=1

14.9. Jacobi sums

14.10. The diagonal cubic, revisited

Chapter 15. Combinatorial number theory

15.1. Partitions

15.2. Jacobi’s triple product identity

15.3. The FreimanRuzsa Theorem

15.4. Expansion and the PlünneckeRuzsa inequality

15.5. Schnirel′man’s Theorem

15.6. Classical additive number theory

15.7. Challenging problems

Further reading for chapter 15

15A. Summing sets modulo 𝑝

15.8. The CauchyDavenport Theorem

15B. Summing sets of integers

15.9. The Frobenius postage stamp problem, III

Chapter 16. The 𝑝adic numbers

16.1. The 𝑝adic norm

16.2. 𝑝adic expansions

16.3. 𝑝adic roots of polynomials

16.4. 𝑝adic factors of a polynomial

Factoring polynomials in ℤ[𝕩] efficiently

Further reading on factoring polynomials

16.5. Possible norms on the rationals

16.6. Power series convergence and the 𝑝adic logarithm

16.7. The 𝑝adic dilogarithm

Further reading on 𝑝adics

Chapter 17. Rational points on elliptic curves

17.1. The group of rational points on an elliptic curve

17.2. Congruent number curves

17.3. No nontrivial rational points by descent

17.4. The group of rational points of 𝑦²=𝑥³𝑥

17.5. Mordell’s Theorem: 𝐸_{𝐴}(ℚ) is finitely generated

Much of the discussion in this chapter is developed from

17.6. Some nice examples

Further reading on the basics of elliptic curves

17A. General Mordell’s Theorem

17.7. The growth of points

17B. Pythagorean triangles of area 6

Integer points

There are many techniques to limit integer points in

17C. 2parts of abelian groups

17.8. 2parts of abelian, arithmetic groups

17D. Waring’s problem

17.9. Waring’s problem

Further reading on Waring’s problem

Hints for exercises

Recommended further reading

Index

Back Cover


Additional Material

Reviews

Not just a list of results and definitions that were hopefully explained in class, this a book for sitting down and engaging with, pen in hand, ready for the exercises interlaced with the exposition. Students learn not just by seeing examples and special cases worked out in advance of a general statement, but by working things out for themselves...One striking feature of this book (and perhaps one argument for a stream of new books on old subjects) is its inclusion of current research in its additional topics...This book will surely address the precocious student.s desire to know what number theory is about now.
Patrick Ingram, York University, CMS Notes 
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 pageturner. How often can you say that about a mathematical textbook? Chapeau!
Marco Abate, The Mathematical Intelligencer 
Andrew Granville has written many wonderful expository articles about number theory (especially patterns in primes), as well as dozens of research articles on many aspects of this field. It is, thus, highly appropriate that he turn all this knowledge into a series of textbooks for number theory. So if you are looking for enrichment in how the world of number theory connects together but formatted as a textbook with familiar topical arrangement, this is a great resource; I can't wait for the next two volumes to appear.
KarlDieter Crisman, MAA Reviews


RequestsReview Copy – for publishers of book reviewsDesk Copy – for instructors who have adopted an AMS textbook for a courseExamination Copy – for faculty considering an AMS textbook for a coursePermission – for use of book, eBook, or Journal contentAccessibility – to request an alternate format of an AMS title
 Book Details
 Table of Contents
 Additional Material
 Reviews
 Requests
Number Theory Revealed: A Masterclass presents a fresh take on congruences, power residues, quadratic residues, primes, and Diophantine equations and presents hot topics like cryptography, factoring, and primality testing. Students are also introduced to beautiful enlightening questions like the structure of Pascal's triangle mod p, Fermat's Last Theorem for polynomials, and modern twists on traditional questions.
This Masterclass edition contains many additional chapters and appendices not found in Number Theory Revealed: An Introduction. It is ideal for instructors who wish to tailor a class to their own interests and gives wellprepared students further opportunities to challenge themselves and push beyond core number theory concepts, serving as a springboard to many current themes in mathematics. Additional topics in A Masterclass include the curvature of circles in a tiling of a circle by circles, the latest discoveries on gaps between primes, magic squares of primes, a new proof of Mordell's Theorem for congruent elliptic curves, as well as links with algebra, analysis, cryptography, and dynamics.
This book is part of Number Theory Revealed: The Series. Find full tables of contents, sample problems, hints, and appendices, as well as updates about forthcoming related volumes here.
About the Author:
Andrew Granville is the Canada Research Chair in Number Theory at the University of Montreal and professor of mathematics at University College London. He has won several international writing prizes for exposition in mathematics, including the 2008 Chauvenet Prize and the 2019 HalmosFord Prize, and is the author of Prime Suspects (Princeton University Press, 2019), a beautifully illustrated graphic novel murder mystery that explores surprising connections between the anatomies of integers and of permutations.
Undergraduate and graduate students interested in introductory number theory.

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

0A. A closed formula for sums of powers

0.5. Formulas for sums of powers of integers, II

0B. Generating functions

0.6. Formulas for sums of powers of integers, III

0.7. The power series view on the Fibonacci numbers

0C. Finding roots of polynomials

0.8. Solving the general cubic

0.9. Solving the general quartic

0.10. Surds

References discussing solvability of polynomials

0D. What is a group?

0.11. Examples and definitions

0.12. Matrices usually don’t commute

0E. Rings and fields

0.13. Mixing addition and multiplication together: Rings and fields

0.14. Algebraic numbers, integers, and units, I

0F. Symmetric polynomials

0.15. The theory of symmetric polynomials

0.16. Some special symmetric polynomials

0.17. Algebraic numbers, integers, and units, II

0G. Constructibility

0.18. Constructible using only compass and ruler

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

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

1B. Computational aspects of the Euclidean algorithm

1.11. Speeding up the Euclidean algorithm

1.12. Euclid’s algorithm works in “polynomial time”

1C. Magic squares

1.13. Turtle power

1.14. Latin squares

1.15. Factoring magic squares

Reference for this appendix

1D. The Frobenius postage stamp problem

1.16. The Frobenius postage stamp problem, I

1E. Egyptian fractions

1.17. Simple fractions

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 𝑑

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

2B. The Euclidean algorithm for polynomials

2.10. The Euclidean algorithm in ℂ[𝕩]

2.11. Common factors over rings: Resultants and discriminants

2.12. Euclidean domains

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

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

3B. Solving linear congruences

3.12. Composite moduli

3.13. Solving linear congruences with several unknowns

3.14. The Chinese Remainder Theorem in general

When the moduli are not coprime

3C. Groups and rings

3.15. A direct sum

3.16. The structure of finite abelian groups

3D. Unique factorization revisited

3.17. The Fundamental Theorem of Arithmetic, clarified

3.18. When unique factorization fails

3.19. Defining ideals and factoring

3.20. Bases for ideals in quadratic fields

3E. Gauss’s approach

3.21. Gauss’s approach to Euclid’s Lemma

3F. Fundamental theorems and factoring polynomials

3.22. The number of distinct roots of polynomials

The Euclidean algorithm for polynomials

Unique factorization of polynomials modulo 𝑝

3.23. Interpreting resultants and discriminants

3.24. Other approaches to resultants and gcds

Additional exercises

3G. Open problems

3.25. The Frobenius postage stamp problem, II

3.26. Egyptian fractions for 3/𝑏

3.27. The 3𝑥+1 conjecture

Further reading on these open problems

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

4A. More multiplicative functions

4.4. Summing multiplicative functions

4.5. Inclusionexclusion and the Möbius function

4.6. Convolutions and the Möbius inversion formula

4.7. The Liouville function

Additional exercises

4B. Dirichlet series and multiplicative functions

4.9. Dirichlet series

4.10. Multiplication of Dirichlet series

4.11. Other Dirichlet series of interest

4C. Irreducible polynomials modulo 𝑝

4.12. Irreducible polynomials modulo 𝑝

4D. The harmonic sum and the divisor function

4.13. The average number of divisors

4.14. The harmonic sum

4.15. Dirichlet’s hyperbola trick

4E. Cyclotomic polynomials

4.16. Cyclotomic polynomials

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

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 GreenTao Theorem

5B. An important proof of infinitely many primes

5.12. Euler’s proof of the infinitude of primes

Reference on Euler’s many contributions

5.13. The sieve of Eratosthenes and estimates for the primes up to 𝑥

5.14. Riemann’s plan for Gauss’s prediction, I

5C. What should be true about primes?

5.15. The GaussCramér model for the primes

Short intervals

Twin primes

5D. Working with Riemann’s zetafunction

5.16. Riemann’s plan for Gauss’s prediction

5.17. Understanding the zeros

An elementary proof

5.18. Reformulations of the Riemann Hypothesis

Primes and complex analysis

5E. Prime patterns: Consequences of the GreenTao Theorem

5.19. Generalized arithmetic progressions of primes

Consecutive prime values of a polynomial

Magic squares of primes

Primes as averages

5F. A panoply of prime proofs

Furstenberg’s (pointset) topological proof

An analytic proof

A proof by irrationality

5G. Searching for primes and prime formulas

5.21. Searching for prime formulas

5.22. Conway’s prime producing machine

5.23. Ulam’s spiral

5.24. Mills’s formula

Further reading on primes in surprising places

5H. Dynamical systems and infinitely many primes

5.25. A simpler formulation

5.26. Different starting points

5.27. Dynamical systems and the infinitude of primes

5.28. Polynomial maps for which 0 is strictly preperiodic

References for this chapter

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

6A. Polynomial solutions of Diophantine equations

6.6. Fermat’s Last Theorem in ℂ[𝕥]

6.7. 𝑎+𝑏=𝑐 in ℂ[𝕥]

6B. No Pythagorean triangle of square area via Euclidean geometry

An algebraic proof, by descent

6.8. A geometric viewpoint

6C. Can a binomial coefficient be a square?

6.9. Small 𝑘

6.10. Larger 𝑘

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

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

7B. Orders and primitive roots

7.15. Constructing primitive roots modulo 𝑝

7.16. Indices / Discrete Logarithms

7.17. Primitive roots modulo prime powers

7.18. Orders modulo composites

7C. Finding 𝑛th roots modulo prime powers

7.19. 𝑛th roots modulo 𝑝

7.20. Lifting solutions

7.21. Finding 𝑛th roots quickly

7D. Orders for finite groups

7.22. Cosets of general groups

7.23. Lagrange and Wilson

7.24. Normal subgroups

7E. Constructing finite fields

7.25. Classification of finite fields

Further reading on arithmetic associated with finite fields

7.26. The product of linear forms in 𝔽_{𝕢}

7F. Sophie Germain and Fermat’s Last Theorem

7.27. Fermat’s Last Theorem and Sophie Germain

7G. Primes of the form 2ⁿ+𝑘

7.28. Covering sets of congruences

7.29. Covering systems for the Fibonacci numbers

A Fibonacci covering system

7.30. The theory of covering systems

Interesting articles on covering systems

7H. Further congruences

7.31. Fermat quotients

Binomial coefficients

Bernoulli numbers modulo 𝑝

Sums of powers of integers modulo 𝑝²

The Wilson quotient

Beyond Fermat’s Little Theorem

Reference for this section

7.32. Frequency of 𝑝divisibility

Fermat quotients

Bernoulli numbers

7I. Primitive prime factors of recurrence sequences

7.33. Primitive prime factors

Prime power divisibility of secondorder linear recurrence sequences

7.34. Closed form identities and sums of powers

7.35. Primitive prime factors and secondorder linear recurrence sequences

References for this chapter

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

8A. Eisenstein’s proof of quadratic reciprocity

8.10. Eisenstein’s elegant proof, 1844

8B. Small quadratic nonresidues

8.11. The least quadratic nonresidue modulo 𝑝

8.12. The smallest prime 𝑞 for which 𝑝 is a quadratic nonresidue modulo 𝑞

8.13. Character sums and the least quadratic nonresidue

8C. The first proof of quadratic reciprocity

8.14. Gauss’s original proof of the law of quadratic reciprocity

8D. Dirichlet characters and primes in arithmetic progressions

8.15. The Legendre symbol and a certain quotient group

8.16. Dirichlet characters

8.17. Dirichlet series and primes in arithmetic progressions

Uniformity questions

8E. Quadratic reciprocity and recurrence sequences

8.18. The Fibonacci numbers modulo 𝑝

8.19. General secondorder linear recurrence sequences modulo 𝑝

8.20. Prime values in recurrence sequences

Chapter 9. Quadratic equations

9.1. Sums of two squares

9.2. The values of 𝑥²+𝑑𝑦²

9.3. Is there a solution to a given quadratic equation?

9.4. Representation of integers by 𝑎𝑥²+𝑏𝑦² with 𝑥,𝑦 rational, and beyond

9.5. The failure of the localglobal principle for quadratic equations in integers

9.6. Primes represented by 𝑥²+5𝑦²

Additional exercises

9A. Proof of the localglobal principle for quadratic equations

9.8. Lattices and quotients

9.9. A better proof of the localglobal principle

9B. Reformulation of the localglobal principle

9.10. The Hilbert symbol

9.11. The HasseMinkowski principle

This is all discussed in detail in Part I of the wonderful book

9C. The number of representations

9.12. Distinct representations as sums of two squares

9D. Descent and the quadratics

9.13. Further solutions through linear algebra

9.14. The Markov equation

9.15. Apollonian circle packing

Further reading on Apollonian packings

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

10A. Pseudoprime tests using square roots of 1

10.8. The difficulty of finding all square roots of 1

10B. Factoring with squares

Random squares

Euler’s sum of squares method

The Continued fractions method

10.9. Factoring with polynomial values

The large prime variation

10C. Identifying primes of a given size

10.10. The ProthPocklingtonLehmer primality test

Secondorder linear recurrences

References for this chapter

10D. Carmichael numbers

10.11. Constructing Carmichael numbers

10.12. Erdős’s construction

The computational evidence

References for this chapter

10E. Cryptosystems based on discrete logarithms

10.13. The DiffieHellman key exchange

10.14. The El Gamal cryptosystem

10F. Running times of algorithms

10.15. P and NP

10.16. Difficult problems

10G. The AKS test

10.17. A computationally quicker characterization of the primes

10.18. A set of extraordinary congruences

Upper bounds on 𝐺

Lower bounds on 𝐺

References for this chapter

10H. Factoring algorithms for polynomials

10.19. Testing polynomials for irreducibility

10.20. Testing whether a polynomial is squarefree

10.21. Factoring a squarefree polynomial modulo 𝑝

References for this chapter

Chapter 11. Rational approximations to real numbers

11.1. The pigeonhole principle

11.2. Pell’s equation

11.3. Descent on solutions of 𝑥²𝑑𝑦²=𝑛,𝑑>0

11.4. Transcendental numbers

11.5. The 𝑎𝑏𝑐conjecture

Further reading for this chapter

Additional exercises

11A. Uniform distribution

11.7. 𝑛𝛼 mod 1

11.8. Bouncing billiard balls

11B. Continued fractions

11.9. Continued fractions for real numbers

11.10. How good are these approximations?

11.11. Periodic continued fractions and Pell’s equation

11.12. Quadratic irrationals and periodic continued fractions

11.13. Solutions to Pell’s equation from a wellselected continued fraction

11.14. Sums of two squares from continued fractions

Modern uses of continued fractions

11C. Twovariable quadratic equations

11.15. Integer solutions to 2variable quadratics

11D. Transcendental numbers

11.16. Diagonalization

11.17. The hunt for transcendental numbers

11.18. Normal numbers

Normal digits of numbers

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

12A. Composition rules: Gauss, Dirichlet, and Bhargava

12.7. Composition and Gauss

12.8. Dirichlet composition

12.9. Bhargava composition

12B. The class group

12.10. A dictionary between binary quadratic forms and ideals

12.11. Elements of order two in the class group

References for this chapter

12C. Binary quadratic forms of positive discriminant

12.12. Binary quadratic forms with positive discriminant, and continued fractions

12.13. The set of automorphisms

12D. Sums of three squares

12.14. Connection between sums of 3 squares and ℎ(𝑑)

12.15. Dirichlet’s class number formula

12E. Sums of four squares

12.16. Sums of four squares

12.17. Quaternions

12.18. The number of representations

12F. Universality

12.19. Universality of quadratic forms

References for this appendix

12G. Integers represented in Apollonian circle packings

12.20. Combining these linear transformations

Further reading on Apollonian packings

Chapter 13. The anatomy of integers

13.1. Rough estimates for the number of integers with a fixed number of prime factors

13.2. The number of prime factors of a typical integer

13.3. The multiplication table problem

13.4. Hardy and Ramanujan’s inequality

13A. Other anatomies

13.5. The anatomy of polynomials in finite fields

13.6. The anatomy of permutations

More on mathematical anatomies

13B. Dirichlet 𝐿functions

13.7. Dirichlet series

Further exercises

Chapter 14. Counting integral and rational points on curves, modulo 𝑝

14.1. Diagonal quadratics

14.2. Counting solutions to a quadratic equation and another proof of quadratic reciprocity

14.3. Cubic equations modulo 𝑝

14.4. The equation 𝐸_{𝑏}:𝑦²=𝑥³+𝑏

14.5. The equation 𝑦²=𝑥³+𝑎𝑥

14.6. A more general viewpoint on counting solutions modulo 𝑝

14A. Gauss sums

14.7. Identities for Gauss sums

14.8. Dirichlet 𝐿functions at 𝑠=1

14.9. Jacobi sums

14.10. The diagonal cubic, revisited

Chapter 15. Combinatorial number theory

15.1. Partitions

15.2. Jacobi’s triple product identity

15.3. The FreimanRuzsa Theorem

15.4. Expansion and the PlünneckeRuzsa inequality

15.5. Schnirel′man’s Theorem

15.6. Classical additive number theory

15.7. Challenging problems

Further reading for chapter 15

15A. Summing sets modulo 𝑝

15.8. The CauchyDavenport Theorem

15B. Summing sets of integers

15.9. The Frobenius postage stamp problem, III

Chapter 16. The 𝑝adic numbers

16.1. The 𝑝adic norm

16.2. 𝑝adic expansions

16.3. 𝑝adic roots of polynomials

16.4. 𝑝adic factors of a polynomial

Factoring polynomials in ℤ[𝕩] efficiently

Further reading on factoring polynomials

16.5. Possible norms on the rationals

16.6. Power series convergence and the 𝑝adic logarithm

16.7. The 𝑝adic dilogarithm

Further reading on 𝑝adics

Chapter 17. Rational points on elliptic curves

17.1. The group of rational points on an elliptic curve

17.2. Congruent number curves

17.3. No nontrivial rational points by descent

17.4. The group of rational points of 𝑦²=𝑥³𝑥

17.5. Mordell’s Theorem: 𝐸_{𝐴}(ℚ) is finitely generated

Much of the discussion in this chapter is developed from

17.6. Some nice examples

Further reading on the basics of elliptic curves

17A. General Mordell’s Theorem

17.7. The growth of points

17B. Pythagorean triangles of area 6

Integer points

There are many techniques to limit integer points in

17C. 2parts of abelian groups

17.8. 2parts of abelian, arithmetic groups

17D. Waring’s problem

17.9. Waring’s problem

Further reading on Waring’s problem

Hints for exercises

Recommended further reading

Index

Back Cover

Not just a list of results and definitions that were hopefully explained in class, this a book for sitting down and engaging with, pen in hand, ready for the exercises interlaced with the exposition. Students learn not just by seeing examples and special cases worked out in advance of a general statement, but by working things out for themselves...One striking feature of this book (and perhaps one argument for a stream of new books on old subjects) is its inclusion of current research in its additional topics...This book will surely address the precocious student.s desire to know what number theory is about now.
Patrick Ingram, York University, CMS Notes 
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 pageturner. How often can you say that about a mathematical textbook? Chapeau!
Marco Abate, The Mathematical Intelligencer 
Andrew Granville has written many wonderful expository articles about number theory (especially patterns in primes), as well as dozens of research articles on many aspects of this field. It is, thus, highly appropriate that he turn all this knowledge into a series of textbooks for number theory. So if you are looking for enrichment in how the world of number theory connects together but formatted as a textbook with familiar topical arrangement, this is a great resource; I can't wait for the next two volumes to appear.
KarlDieter Crisman, MAA Reviews