Cover -- Title page -- Contents -- 0 Introduction -- Number Theory and Mathematical Thinking -- Note on the approach and organization -- Methods of thought -- Acknowledgments -- 1 Divide and Conquer -- Divisibility in the Natural Numbers -- Definitions and examples -- Divisibility and congruence -- The Division Algorithm -- Greatest common divisors and linear Diophantine equations -- Linear Equations Through the Ages -- 2 Prime Time -- The Prime Numbers -- Fundamental Theorem of Arithmetic -- Applications of the Fundamental Theorem of Arithmetic -- The infinitude of primes -- Primes of special form -- The distribution of primes -- From Antiquity to the Internet -- 3 A Modular World -- Thinking Cyclically -- Powers and polynomials modulo n -- Linear congruences -- Systems of linear congruences: the Chinese Remainder Theorem -- A Prince and a Master -- 4 Fermat's Little Theorem and Euler's Theorem -- Abstracting the Ordinary -- Orders of an integer modulo n -- Fermat's Little Theorem -- An alternative route to Fermat's Little Theorem -- Euler's Theorem and Wilson's Theorem -- Fermat, Wilson and . . . Leibniz? -- 5 Public Key Cryptography -- Public Key Codes and RSA -- Public key codes -- Overview of RSA -- Let's decrypt -- Hard Problems -- 6 Polynomial Congruences and Primitive Roots -- Higher Order Congruences -- Lagrange's Theorem -- Primitive roots -- Euler's phi-function and sums of divisors -- Euler's phi-function is multiplicative -- Roots modulo a number -- Sophie Germain is Germane, Part I -- 7 The Golden Rule: Quadratic Reciprocity -- Quadratic Congruences -- Quadratic residues -- Gauss' Lemma and quadratic reciprocity -- Sophie Germain is germane, Part II -- 8 Pythagorean Triples, Sums of Squares, and Fermat's Last Theorem -- Congruences to Equations -- Pythagorean triples -- Sums of squares -- Pythagorean triples revisited.

Fermat's Last Theorem -- Who's Represented? -- Sums of squares -- Sums of cubes, taxicabs, and Fermat's Last Theorem -- 9 Rationals Close to Irrationals and the Pell Equation -- Diophantine Approximation and Pell Equations -- A plunge into rational approximation -- Out with the trivial -- New solutions from old -- Securing the elusive solution -- The structure of the solutions to the Pell equations -- Bovine Math -- 10 The Search for Primes -- Primality Testing -- Is it prime? -- Fermat's Little Theorem and probable primes -- AKS primality -- Record Primes -- A Mathematical Induction: The Domino Effect -- The Infinitude Of Facts -- Gauss' formula -- Another formula -- On your own -- Strong induction -- On your own -- Index -- About the Authors.