2019;
264 pp;
Hardcover

MSC: Primary 11;

**Print ISBN: 978-1-4704-4157-9
Product Code: MBK/126**

List Price: $69.00

AMS Member Price: $55.20

MAA Member Price: $62.10

**Electronic ISBN: 978-1-4704-5423-4
Product Code: MBK/126.E**

List Price: $69.00

AMS Member Price: $55.20

MAA Member Price: $62.10

#### You may also like

#### Supplemental Materials

# Number Theory Revealed: An Introduction

Share this page
*Andrew Granville*

Number Theory Revealed: An Introduction presents a fresh
take on congruences, power residues, quadratic residues, primes, and
Diophantine equations, as well as 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 book provides careful
coverage of all core topics in a standard introductory number theory
course with pointers to some exciting further directions.

An expanded edition,
Number Theory
Revealed: A Masterclass, offers a more comprehensive approach,
adding additional material in further chapters and appendices. It is
ideal for instructors who wish to tailor a class to their own
interests and gives well-prepared students further opportunities to
challenge themselves and push beyond core number theory concepts,
serving as a springboard to many current themes in mathematics.

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 Halmos-Ford 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.

#### Readership

Undergraduate and graduate students interested in introductory number theory.

#### Table of Contents

# Table of Contents

## Number Theory Revealed: An Introduction

- Cover Cover11
- Title page iii4
- Preface xiii14
- Gauss’s Disquisitiones Arithmeticae xix20
- Notation xxi22
- Prerequisites xxiii24
- Preliminary Chapter on Induction 126
- 0.1. Fibonacci numbers and other recurrence sequences 126
- 0.2. Formulas for sums of powers of integers 328
- 0.3. The binomial theorem, Pascal’s triangle, and the binomial coefficients 429
- Articles with further thoughts on factorials and binomial coefficients 631
- Additional exercises 631
- A paper that questions one’s assumptions is 833

- Chapter 1. The Euclidean algorithm 1136
- Appendix 1A. Reformulating the Euclidean algorithm 2348
- Chapter 2. Congruences 2954
- Appendix 2A. Congruences in the language of groups 3964
- Chapter 3. The basic algebra of number theory 4368
- 3.1. The Fundamental Theorem of Arithmetic 4368
- 3.2. Abstractions 4570
- 3.3. Divisors using factorizations 4772
- 3.4. Irrationality 4974
- 3.5. Dividing in congruences 5075
- 3.6. Linear equations in two unknowns 5277
- 3.7. Congruences to several moduli 5479
- 3.8. Square roots of 1 (mod 𝑛) 5681
- Additional exercises 5883
- Reference on the many proofs that √2 is irrational 5984

- Appendix 3A. Factoring binomial coefficients and Pascal’s triangle modulo 𝑝 6186
- Chapter 4. Multiplicative functions 6792
- Appendix 4A. More multiplicative functions 7499
- Chapter 5. The distribution of prime numbers 81106
- 5.1. Proofs that there are infinitely many primes 81106
- 5.2. Distinguishing primes 83108
- 5.3. Primes in certain arithmetic progressions 85110
- 5.4. How many primes are there up to 𝑥? 86111
- 5.5. Bounds on the number of primes 89114
- 5.6. Gaps between primes 91116
- Further reading on hot topics in this section 93118
- 5.7. Formulas for primes 93118
- Additional exercises 95120

- Appendix 5A. Bertrand’s postulate and beyond 97122
- Bonus read: A review of prime problems 101126
- Chapter 6. Diophantine problems 109134
- 6.1. The Pythagorean equation 109134
- 6.2. No solutions to a Diophantine equation through descent 112137
- No solutions through prime divisibility 112137
- No solutions through geometric descent 113138
- 6.3. Fermat’s “infinite descent” 114139
- 6.4. Fermat’s Last Theorem 115140
- A brief history of equation solving 116141
- References for this chapter 117142
- Additional exercises 117142

- Appendix 6A. Polynomial solutions of Diophantine equations 119144
- Chapter 7. Power residues 123148
- 7.1. Generating the multiplicative group of residues 124149
- 7.2. Fermat’s Little Theorem 125150
- 7.3. Special primes and orders 128153
- 7.4. Further observations 128153
- 7.5. The number of elements of a given order, and primitive roots 129154
- 7.6. Testing for composites, pseudoprimes, and Carmichael numbers 133158
- 7.7. Divisibility tests, again 134159
- 7.8. The decimal expansion of fractions 134159
- 7.9. Primes in arithmetic progressions, revisited 136161
- References for this chapter 137162
- Additional exercises 137162

- Appendix 7A. Card shuffling and Fermat’s Little Theorem 140165
- Chapter 8. Quadratic residues 147172
- 8.1. Squares modulo prime 𝑝 147172
- 8.2. The quadratic character of a residue 149174
- 8.3. The residue -1 152177
- 8.4. The residue 2 153178
- 8.5. The law of quadratic reciprocity 155180
- 8.6. Proof of the law of quadratic reciprocity 157182
- 8.7. The Jacobi symbol 159184
- 8.8. The squares modulo 𝑚 161186
- Additional exercises 162187
- Further reading on Euclidean proofs 165190

- Appendix 8A. Eisenstein’s proof of quadratic reciprocity 167192
- Chapter 9. Quadratic equations 173198
- 9.1. Sums of two squares 173198
- 9.2. The values of 𝑥²+𝑑𝑦² 176201
- 9.3. Is there a solution to a given quadratic equation? 177202
- 9.4. Representation of integers by 𝑎𝑥²+𝑏𝑦² with 𝑥,𝑦 rational, and beyond 180205
- 9.5. The failure of the local-global principle for quadratic equations in integers 181206
- 9.6. Primes represented by 𝑥²+5𝑦² 181206
- Additional exercises 182207

- Appendix 9A. Proof of the local-global principle for quadratic equations 184209
- Chapter 10. Square roots and factoring 189214
- 10.1. Square roots modulo 𝑛 189214
- 10.2. Cryptosystems 190215
- 10.3. RSA 192217
- 10.4. Certificates and the complexity classes P and NP 194219
- 10.5. Polynomial time primality testing 196221
- 10.6. Factoring methods 197222
- References: See [CP05] and [Knu98], as well as: 199224
- Additional exercises 199224

- Appendix 10A. Pseudoprime tests using square roots of 1 200225
- Chapter 11. Rational approximations to real numbers 205230
- Appendix 11A. Uniform distribution 220245
- Chapter 12. Binary quadratic forms 227252
- 12.1. Representation of integers by binary quadratic forms 228253
- 12.2. Equivalence classes of binary quadratic forms 230255
- 12.3. Congruence restrictions on the values of a binary quadratic form 231256
- 12.4. Class numbers 232257
- 12.5. Class number one 233258
- References for this chapter 236261
- Additional exercises 236261

- Appendix 12A. Composition rules: Gauss, Dirichlet, and Bhargava 240265
- Hints for exercises 251276
- Recommended further reading 261286
- Index 263288
- Back Cover Back Cover1290