NUMBER THEORY REVEALED : an introduction

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. Cover Number Theory Revealed: An Introduction Copyright Dedication Epigraph Contents 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 Additional exercises 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 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 Additional exercises Reference on the many proofs that 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. Additional exercises Appendix 4A. More multiplicative functions 4.4. Summing multiplicative functions 4.5. Inclusion-exclusion and the M ̈obius function 4.6. Convolutions and the M ̈obius 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.4. How many primes are there up to Further reading on hot topics in this section Additional exercises Appendix 5A. Bertrand’s postulate and beyond 5.9. Bertrand’s postulate 5.10. The theorem of Sylvester and Schur 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 6.3. Fermat’s “infinite descent” 6.4. Fermat’s Last Theorem 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.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 8.4. The residue 8.5. The law of quadratic reciprocity 8.6. Proof of the law of quadratic reciprocity 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 9.3. Is there a solution to a given quadratic equation? 9.4. Representation of integers by with rational, and beyond 9.6. Primes represented by 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 10.5. Polynomial time primality testing 10.6. Factoring methods Appendix 10A. Pseudoprimetests using square roots of 1 Chapter 11. Rational approximations to real numbers 11.1. The pigeonhole principle 11.2. Pell’s equation 11.4. Transcendental numbers Further reading for this chapter Additional exercises Appendix 11A. Uniform distribution 11.7. nα 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 composition5 Hints for exercises Recommended further reading Index

Number Theory Revealed: An Introduction acquaints undergraduates with the "Queen of Mathematics". The text offers 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$ and modern twists on traditional questions like the values represented by binary quadratic forms and large solutions of equations. Each chapter includes an "elective appendix" with additional reading, projects, and references.An expanded edition, Number Theory Revealed: A Masterclass, offers a more comprehensive approach to these core topics and adds additional material in further chapters and appendices, allowing instructors to create an individualized course tailored to their own (and their students') interests.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.

Number Theory Revealed: An Introduction acquaints undergraduates with the “Queen of Mathematics”. The text offers 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$ and modern twists on traditional questions like the values represented by binary quadratic forms and large solutions of equations. Each chapter includes an “elective appendix” with additional reading, projects, and references. An expanded edition, Number Theory Revealed: A Masterclass, offers a more comprehensive approach to these core topics and adds additional material in further chapters and appendices, allowing instructors to create an individualized course tailored to their own (and their students') interests. 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. Number Theory Revealed: A Masterclass acquaints enthusiastic students with the "Queen of Mathematics". The text offers 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 and modern twists on traditional questions like the values represented by binary quadratic forms, the anatomy of integers, and elliptic curves. This Masterclass edition contains many additional chapters and appendices not found in Number Theory Revealed: An Introduction, highlighting beautiful developments and inspiring other subjects in mathematics (like algebra). This allows instructors to tailor a course suited to their own (and their students') interests. There are new yet accessible topics like the curvature of circles in a tiling of a circle by circles, the latest discoveries on gaps between primes, a new proof of Mordell's Theorem for congruent elliptic curves, and a discussion of the abc-conjecture including its proof for polynomials Number Theory Revealed: An Introduction Acquaints Undergraduates With The “queen Of Mathematics”. The Text Offers 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 P And Modern Twists On Traditional Questions Like The Values Represented By Binary Quadratic Forms And Large Solutions Of Equations. Each Chapter Includes An “elective Appendix” With Additional Reading, Projects, And References. An Expanded Edition, Number Theory Revealed: A Masterclass, Offers A More Comprehensive Approach To These Core Topics And Adds Additional Material In Further Chapters And Appendices, Allowing Instructors To Create An Individualized Course Tailored To Their Own (and Their Students') Interests.