Elementary Number Theory

PrefaceNew To This Edition1 Preliminaries1.1 Mathematical Induction1.2 The Binomial Theorem2 Divisibility Theory in the Integers2.1 Early Number Theory2.1 The Division Algorithm2.2 The Greatest Common Divisor2.3 The Euclidean Algorithm2.4 The Diophantine Equation ax + by = c3 Primes and Their Distribution3.1 The Fundamental Theorem of Arithmetic3.2 The Sieve of Eratosthenes3.3 The Goldbach Conjecture4 The Theory of Congruences4.1 Carl Friedrich Gauss4.2 Basic Properties of Congruence4.3 Binary and Decimal Representations of Integers4.4 Linear Congruences and the Chinese Remainder Theorem5 Fermat's Theorem5.1 Pierre de Fermat5.2 Fermat's Little Theorem and Pseudoprimes5.3 Wilson's Theorem5.4 The Fermat-Kraitchik Factorization Method6 Number-Theoretic Functions6.1 The Sum and Number of Divisors6.2 The Möbius Inversion Formula6.3 The Greatest Integer Function6.4 An Application to the Calendar7 Euler's Generalization of Fermat's Theorem7.1 Leonhard Euler7.2 Euler's Phi-Function7.3 Euler's Theorem7.4 Some Properties of the Phi-Function8 Primitive Roots and Indices8.1 The Order of an Integer Modulo n8.2 Primitive Roots for Primes8.3 Composite Numbers Having Primitive Roots8.4 The Theory of Indices9 The Quadratic Reciprocity Law9.1 Euler's Criterion9.2 The Legendre Symbol and Its Properties9.3 Quadratic Reciprocity9.4 Quadratic Congruences with Composite Moduli10 Introduction to Cryptography10.1 From Caesar Cipher to Public Key Cryptography10.2 The Knapsack Cryptosystem10.3 An Application of Primitive Roots to Cryptography11 Numbers of Special Form11.1 Marin Mersenne11.2 Perfect Numbers11.3 Mersenne Primes and Amicable Numbers11.4 Fermat Numbers12 Certain Nonlinear Diophantine Equations12.1 The Equation x2 + y2 = z212.2 Fermat's Last Theorem13 Representation of Integers as Sums of Squares13.1 Joseph Louis Lagrange13.2 Sums of Two Squares13.3 Sums of More Than Two Squares14 Fibonacci Numbers14.1 Fibonacci14.2 The Fibonacci Sequence14.3 Certain Identities Involving Fibonacci Numbers15 Continued Fractions15.1 Srinivasa Ramanujan15.2 Finite Continued Fractions15.3 Infinite Continued Fractions15.4 Pell's Equation16 Some Twentieth-Century Developments16.1 Hardy, Dickson, and Erdös16.2 Primality Testing and Factorization16.3 An Application to Factoring: Remote Coin Flipping16.4 The Prime Number Theorem and Zeta FunctionMiscellaneous ProblemsAppendixesGeneral ReferencesSuggested Further ReadingTablesAnswers to Selected ProblemsIndex