2019;
587 pp;
Hardcover

MSC: Primary 11;

**Print ISBN: 978-1-4704-4158-6
Product Code: MBK/127**

List Price: $99.00

AMS Member Price: $79.20

MAA Member Price: $89.10

**Electronic ISBN: 978-1-4704-5424-1
Product Code: MBK/127.E**

List Price: $99.00

AMS Member Price: $79.20

MAA Member Price: $89.10

#### You may also like

#### Supplemental Materials

# Number Theory Revealed: A Masterclass

Share this page
*Andrew Granville*

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

#### Reviews & Endorsements

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.

-- Karl-Dieter Crisman, MAA Reviews

#### Table of Contents

# Table of Contents

## Number Theory Revealed: A Masterclass

Table of Contents pages: 1 2 3

- 6.2. No solutions to a Diophantine equation through descent 247247
- No solutions through prime divisibility 247247
- No solutions through geometric descent 248248
- 6.3. Fermat’s “infinite descent” 249249
- 6.4. Fermat’s Last Theorem 250250
- A brief history of equation solving 251251
- References for this chapter 252252
- Additional exercises 252252
- 6A. Polynomial solutions of Diophantine equations 254254
- 6.6. Fermat’s Last Theorem in ℂ[𝕥] 254254
- 6.7. 𝑎+𝑏=𝑐 in ℂ[𝕥] 255255
- 6B. No Pythagorean triangle of square area via Euclidean geometry 258258
- An algebraic proof, by descent 258258
- 6.8. A geometric viewpoint 259259
- 6C. Can a binomial coefficient be a square? 262262
- 6.9. Small 𝑘 262262
- 6.10. Larger 𝑘 263263

- Chapter 7. Power residues 264264
- 7.1. Generating the multiplicative group of residues 265265
- 7.2. Fermat’s Little Theorem 266266
- 7.3. Special primes and orders 269269
- 7.4. Further observations 269269
- 7.5. The number of elements of a given order, and primitive roots 270270
- 7.6. Testing for composites, pseudoprimes, and Carmichael numbers 274274
- 7.7. Divisibility tests, again 275275
- 7.8. The decimal expansion of fractions 275275
- 7.9. Primes in arithmetic progressions, revisited 277277
- References for this chapter 278278
- Additional exercises 278278
- 7A. Card shuffling and Fermat’s Little Theorem 281281
- 7.11. Card shuffling and orders modulo 𝑛 281281
- 7.12. The “necklace proof” of Fermat’s Little Theorem 283283
- More combinatorics and number theory 284284
- 7.13. Taking powers efficiently 284284
- 7.14. Running time: The desirability of polynomial time algorithms 285285
- 7B. Orders and primitive roots 287287
- 7.15. Constructing primitive roots modulo 𝑝 287287
- 7.16. Indices / Discrete Logarithms 289289
- 7.17. Primitive roots modulo prime powers 289289
- 7.18. Orders modulo composites 292292
- 7C. Finding 𝑛th roots modulo prime powers 294294
- 7.19. 𝑛th roots modulo 𝑝 294294
- 7.20. Lifting solutions 295295
- 7.21. Finding 𝑛th roots quickly 296296
- 7D. Orders for finite groups 298298
- 7.22. Cosets of general groups 298298
- 7.23. Lagrange and Wilson 299299
- 7.24. Normal subgroups 300300
- 7E. Constructing finite fields 302302
- 7.25. Classification of finite fields 302302
- Further reading on arithmetic associated with finite fields 304304
- 7.26. The product of linear forms in 𝔽_{𝕢} 305305
- 7F. Sophie Germain and Fermat’s Last Theorem 307307
- 7.27. Fermat’s Last Theorem and Sophie Germain 308308
- 7G. Primes of the form 2ⁿ+𝑘 309309
- 7.28. Covering sets of congruences 309309
- 7.29. Covering systems for the Fibonacci numbers 310310
- A Fibonacci covering system 311311
- 7.30. The theory of covering systems 311311
- Interesting articles on covering systems 312312
- 7H. Further congruences 313313
- 7.31. Fermat quotients 313313
- Binomial coefficients 314314
- Bernoulli numbers modulo 𝑝 315315
- Sums of powers of integers modulo 𝑝² 316316
- The Wilson quotient 316316
- Beyond Fermat’s Little Theorem 317317
- Reference for this section 317317
- 7.32. Frequency of 𝑝-divisibility 318318
- Fermat quotients 318318
- Bernoulli numbers 318318
- 7I. Primitive prime factors of recurrence sequences 319319
- 7.33. Primitive prime factors 319319
- Prime power divisibility of second-order linear recurrence sequences 320320
- 7.34. Closed form identities and sums of powers 321321
- 7.35. Primitive prime factors and second-order linear recurrence sequences 321321
- References for this chapter 323323

- Chapter 8. Quadratic residues 324324
- 8.1. Squares modulo prime 𝑝 324324
- 8.2. The quadratic character of a residue 326326
- 8.3. The residue -1 329329
- 8.4. The residue 2 330330
- 8.5. The law of quadratic reciprocity 332332
- 8.6. Proof of the law of quadratic reciprocity 334334
- 8.7. The Jacobi symbol 336336
- 8.8. The squares modulo 𝑚 338338
- Additional exercises 339339
- Further reading on Euclidean proofs 342342
- 8A. Eisenstein’s proof of quadratic reciprocity 344344
- 8.10. Eisenstein’s elegant proof, 1844 344344
- 8B. Small quadratic non-residues 348348
- 8.11. The least quadratic non-residue modulo 𝑝 348348
- 8.12. The smallest prime 𝑞 for which 𝑝 is a quadratic non-residue modulo 𝑞 349349
- 8.13. Character sums and the least quadratic non-residue 350350
- 8C. The first proof of quadratic reciprocity 352352
- 8.14. Gauss’s original proof of the law of quadratic reciprocity 352352
- 8D. Dirichlet characters and primes in arithmetic progressions 355355
- 8.15. The Legendre symbol and a certain quotient group 355355
- 8.16. Dirichlet characters 356356
- 8.17. Dirichlet series and primes in arithmetic progressions 359359
- Uniformity questions 361361
- 8E. Quadratic reciprocity and recurrence sequences 362362
- 8.18. The Fibonacci numbers modulo 𝑝 362362
- 8.19. General second-order linear recurrence sequences modulo 𝑝 363363
- 8.20. Prime values in recurrence sequences 364364

- Chapter 9. Quadratic equations 366366
- 9.1. Sums of two squares 366366
- 9.2. The values of 𝑥²+𝑑𝑦² 369369
- 9.3. Is there a solution to a given quadratic equation? 370370
- 9.4. Representation of integers by 𝑎𝑥²+𝑏𝑦² with 𝑥,𝑦 rational, and beyond 373373
- 9.5. The failure of the local-global principle for quadratic equations in integers 374374
- 9.6. Primes represented by 𝑥²+5𝑦² 374374
- Additional exercises 375375
- 9A. Proof of the local-global principle for quadratic equations 377377
- 9.8. Lattices and quotients 377377
- 9.9. A better proof of the local-global principle 380380
- 9B. Reformulation of the local-global principle 382382
- 9.10. The Hilbert symbol 382382
- 9.11. The Hasse-Minkowski principle 384384
- This is all discussed in detail in Part I of the wonderful book 384384
- 9C. The number of representations 385385
- 9.12. Distinct representations as sums of two squares 385385
- 9D. Descent and the quadratics 389389
- 9.13. Further solutions through linear algebra 389389
- 9.14. The Markov equation 390390
- 9.15. Apollonian circle packing 390390
- Further reading on Apollonian packings 393393

- Chapter 10. Square roots and factoring 394394
- 10.1. Square roots modulo 𝑛 394394
- 10.2. Cryptosystems 395395
- 10.3. RSA 397397
- 10.4. Certificates and the complexity classes P and NP 399399
- 10.5. Polynomial time primality testing 401401
- 10.6. Factoring methods 402402
- References: See [CP05] and [Knu98], as well as: 404404
- Additional exercises 404404
- 10A. Pseudoprime tests using square roots of 1 405405
- 10.8. The difficulty of finding all square roots of 1 405405
- 10B. Factoring with squares 409409
- Random squares 409409
- Euler’s sum of squares method 409409
- The Continued fractions method 410410
- 10.9. Factoring with polynomial values 410410
- The large prime variation 411411
- 10C. Identifying primes of a given size 412412
- 10.10. The Proth-Pocklington-Lehmer primality test 413413
- Second-order linear recurrences 414414
- References for this chapter 415415
- 10D. Carmichael numbers 416416
- 10.11. Constructing Carmichael numbers 416416
- 10.12. Erdős’s construction 417417
- The computational evidence 419419
- References for this chapter 419419
- 10E. Cryptosystems based on discrete logarithms 420420
- 10.13. The Diffie-Hellman key exchange 420420
- 10.14. The El Gamal cryptosystem 421421
- 10F. Running times of algorithms 422422
- 10.15. P and NP 422422
- 10.16. Difficult problems 423423
- 10G. The AKS test 424424
- 10.17. A computationally quicker characterization of the primes 425425
- 10.18. A set of extraordinary congruences 425425
- Upper bounds on |𝐺| 426426
- Lower bounds on |𝐺| 427427
- References for this chapter 427427
- 10H. Factoring algorithms for polynomials 428428
- 10.19. Testing polynomials for irreducibility 428428
- 10.20. Testing whether a polynomial is squarefree 429429
- 10.21. Factoring a squarefree polynomial modulo 𝑝 430430
- References for this chapter 431431

- Chapter 11. Rational approximations to real numbers 432432
- 11.1. The pigeonhole principle 432432
- 11.2. Pell’s equation 435435
- 11.3. Descent on solutions of 𝑥²-𝑑𝑦²=𝑛,𝑑>0 439439
- 11.4. Transcendental numbers 440440
- 11.5. The 𝑎𝑏𝑐-conjecture 443443
- Further reading for this chapter 445445
- Additional exercises 445445
- 11A. Uniform distribution 447447
- 11.7. 𝑛𝛼 mod 1 447447
- 11.8. Bouncing billiard balls 449449
- 11B. Continued fractions 452452
- 11.9. Continued fractions for real numbers 453453
- 11.10. How good are these approximations? 455455
- 11.11. Periodic continued fractions and Pell’s equation 456456
- 11.12. Quadratic irrationals and periodic continued fractions 458458
- 11.13. Solutions to Pell’s equation from a well-selected continued fraction 460460
- 11.14. Sums of two squares from continued fractions 465465
- Modern uses of continued fractions 466466
- 11C. Two-variable quadratic equations 467467
- 11.15. Integer solutions to 2-variable quadratics 467467
- 11D. Transcendental numbers 468468
- 11.16. Diagonalization 468468
- 11.17. The hunt for transcendental numbers 469469
- 11.18. Normal numbers 470470
- Normal digits of numbers 471471

- Chapter 12. Binary quadratic forms 472472