| |
| |
| Preface | |
| |
| |
| New to This Edition | |
| |
| |
| |
| Preliminaries | |
| |
| |
| |
| Mathematical Induction | |
| |
| |
| |
| The Binomial Theorem | |
| |
| |
| |
| Divisibility Theory in the Integers | |
| |
| |
| |
| Early Number Theory | |
| |
| |
| |
| The Division Algorithm | |
| |
| |
| |
| The Greatest Common Divisor | |
| |
| |
| |
| The Euclidean Algorithm | |
| |
| |
| |
| The Diophantine Equation ax + by = c | |
| |
| |
| |
| Primes and Their Distribution | |
| |
| |
| |
| The Fundamental Theorem of Arithmetic | |
| |
| |
| |
| The Sieve of Eratosthenes | |
| |
| |
| |
| The Goldbach Conjecture | |
| |
| |
| |
| The Theory of Congruences | |
| |
| |
| |
| Carl Friedrich Gauss | |
| |
| |
| |
| Basic Properties of Congruence | |
| |
| |
| |
| Binary and Decimal Representations of Integers | |
| |
| |
| |
| Linear Congruences and the Chinese Remainder Theorem | |
| |
| |
| |
| Fermat's Theorem | |
| |
| |
| |
| Pierre de Fermat | |
| |
| |
| |
| Fermat's Little Theorem and Pseudoprimes | |
| |
| |
| |
| Wilson's Theorem | |
| |
| |
| |
| The Fermat-Kraitchik Factorization Method | |
| |
| |
| |
| Number-Theoretic Functions | |
| |
| |
| |
| The Sum and Number of Divisors | |
| |
| |
| |
| The M�bius Inversion Formula | |
| |
| |
| |
| The Greatest Integer Function | |
| |
| |
| |
| An Application to the Calendar | |
| |
| |
| |
| Euler's Generalization of Fermat's Theorem | |
| |
| |
| |
| Leonhard Euler | |
| |
| |
| |
| Euler's Phi-Function | |
| |
| |
| |
| Euler's Theorem | |
| |
| |
| |
| Some Properties of the Phi-Function | |
| |
| |
| |
| Primitive Roots and Indices | |
| |
| |
| |
| The Order of an Integer Modulo n | |
| |
| |
| |
| Primitive Roots for Primes | |
| |
| |
| |
| Composite Numbers Having Primitive Roots | |
| |
| |
| |
| The Theory of Indices | |
| |
| |
| |
| The Quadratic Reciprocity Law | |
| |
| |
| |
| Euler's Criterion | |
| |
| |
| |
| The Legendre Symbol and Its Properties | |
| |
| |
| |
| Quadratic Reciprocity | |
| |
| |
| |
| Quadratic Congruences with Composite Moduli | |
| |
| |
| |
| Introduction to Cryptography | |
| |
| |
| |
| From Caesar Cipher to Public Key Cryptography | |
| |
| |
| |
| The Knapsack Cryptosystem | |
| |
| |
| |
| An Application of Primitive Roots to Cryptography | |
| |
| |
| |
| Numbers of Special Form | |
| |
| |
| |
| Marin Mersenne | |
| |
| |
| |
| Perfect Numbers | |
| |
| |
| |
| Mersenne Primes and Amicable Numbers | |
| |
| |
| |
| Fermat Numbers | |
| |
| |
| |
| Certain Nonlinear Diophantine Equations | |
| |
| |
| |
| The Equation x<sup>2</sup> + y<sup>2</sup> = z<sup>2</sup> | |
| |
| |
| |
| Fermat's Last Theorem | |
| |
| |
| |
| Representation of Integers as Sums of Squares | |
| |
| |
| |
| Joseph Louis Lagrange | |
| |
| |
| |
| Sums of Two Squares | |
| |
| |
| |
| Sums of More Than Two Squares | |
| |
| |
| |
| Fibonacci Numbers | |
| |
| |
| |
| Fibonacci | |
| |
| |
| |
| The Fibonacci Sequence | |
| |
| |
| |
| Certain Identities Involving Fibonacci Numbers | |
| |
| |
| |
| Continued Fractions | |
| |
| |
| |
| Srinivasa Ramanujan | |
| |
| |
| |
| Finite Continued Fractions | |
| |
| |
| |
| Infinite Continued Fractions | |
| |
| |
| |
| Farey Fractions | |
| |
| |
| |
| Pell's Equation | |
| |
| |
| |
| Some Modern Developments | |
| |
| |
| |
| Hardy, Dickson, and Erd�s | |
| |
| |
| |
| Primality Testing and Factorization | |
| |
| |
| |
| An Application to Factoring: Remote Coin Flipping | |
| |
| |
| |
| The Prime Number Theorem and Zeta Function | |
| |
| |
| Miscellaneous Problems | |
| |
| |
| Appendixes | |
| |
| |
| General References | |
| |
| |
| Suggested Further Reading | |
| |
| |
| Tables | |
| |
| |
| Answers to Selected Problems | |
| |
| |
| Index | |