Elementary Number Theory

Elementary Number Theory, 7e, by David M. Burton Table of Contents Preface New to this Edition 1Preliminaries 1.1Mathematical Induction 1.2The Binomial Theorem 2Divisibility Theory in the Integers 2.1Early Number Theory 2.2The Division Algorithm 2.3The Greatest Common Divisor 2.4The Euclidean Algorithm 2.5The Diophantine Equation 3Primes and Their Distribution 3.1The Fundamental Theorem of Arithmetic 3.2The Sieve of Eratosthenes 3.3The Goldbach Conjecture 4The Theory of Congruences 4.1Carl Friedrich Gauss 4.2Basic Properties of Congruence 4.3Binary and Decimal Representations of Integers 4.4Linear Congruences and the Chinese Remainder Theorem 5Fermat’s Theorem 5.1Pierre de Fermat 5.2Fermat’s Little Theorem and Pseudoprimes 5.3Wilson’s Theorem 5.4The Fermat-Kraitchik Factorization Method 6Number-Theoretic Functions 6.1The Sum and Number of Divisors 6.2 The Möbius Inversion Formula 6.3The Greatest Integer Function 6.4An Application to the Calendar 7Euler’s Generalization of Fermat’s Theorem 7.1Leonhard Euler 7.2Euler’s Phi-Function 7.3Euler’s Theorem 7.4Some Properties of the Phi-Function 8Primitive Roots and Indices 8.1The Order of an Integer Modulo n 8.2Primitive Roots for Primes 8.3Composite Numbers Having Primitive Roots 8.4The Theory of Indices 9The Quadratic Reciprocity Law 9.1Euler’s Criterion 9.2The Legendre Symbol and Its Properties 9.3Quadratic Reciprocity 9.4Quadratic Congruences with Composite Moduli 10Introduction to Cryptography 10.1From Caesar Cipher to Public Key Cryptography 10.2The Knapsack Cryptosystem 10.3An Application of Primitive Roots to Cryptography 11Numbers of Special Form 11.1Marin Mersenne 11.2Perfect Numbers 11.3Mersenne Primes and Amicable Numbers 11.4Fermat Numbers 12Certain Nonlinear Diophantine Equations 12.1The Equation 12.2Fermat’s Last Theorem 13Representation of Integers as Sums of Squares 13.1Joseph Louis Lagrange 13.2Sums of Two Squares 13.3Sums of More Than Two Squares 14Fibonacci Numbers 14.1Fibonacci 14.2The Fibonacci Sequence 14.3Certain Identities Involving Fibonacci Numbers 15Continued Fractions 15.1Srinivasa Ramanujan 15.2Finite Continued Fractions 15.3Infinite Continued Fractions 15.4Farey Fractions 15.5Pell’s Equation 16Some Recent Developments 16.1Hardy, Dickson, and Erdös 16.2Primality Testing and Factorization 16.3An Application to Factoring: Remote Coin Flipping 16.4The Prime Number Theorem and Zeta Function Miscellaneous Problems Appendixes General References Suggested Further Reading Tables Answers to Selected Problems Index