| |
| |
| Preface | |
| |
| |
| About This Book | |
| |
| |
| Features | |
| |
| |
| |
| Preliminaries | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Conjectures, Theorems, and Proofs | |
| |
| |
| |
| Well-Ordering and Induction | |
| |
| |
| Well-Ordering Principle | |
| |
| |
| |
| Sigma Notation and Product Notation | |
| |
| |
| |
| Binomial Coefficients | |
| |
| |
| |
| Greatest Integer Function | |
| |
| |
| Review Exercises | |
| |
| |
| |
| Divisibility | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Divisibility, Greatest Common Divisor, Euclid's Algorithm | |
| |
| |
| Greatest Common Divisor via Euclid's Algorithm | |
| |
| |
| |
| Least Common Multiple | |
| |
| |
| |
| Representations of Integers | |
| |
| |
| Decimal Representations of Integers | |
| |
| |
| Binary Representations of Integers | |
| |
| |
| Review Exercises | |
| |
| |
| |
| Primes | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Primes, Prime Counting Function, Prime Number Theorem | |
| |
| |
| Test of Primality by Trial Division | |
| |
| |
| |
| Sieve of Eratosthenes, Canonical Factorization, Fundamental Theorem of Arithmetic | |
| |
| |
| Sieve of Eratosthenes | |
| |
| |
| Determining the Canonical Factorization of a Natural Number | |
| |
| |
| Review Exercises | |
| |
| |
| |
| Congruences | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Congruences and Equivalence Relations | |
| |
| |
| Equivalence Relations | |
| |
| |
| |
| Linear Congruences | |
| |
| |
| |
| Linear Diophantine Equations and the Chinese Remainder Theorem | |
| |
| |
| |
| Polynomial Congruences | |
| |
| |
| |
| Modular Arithmetic: Fermat's Theorem | |
| |
| |
| |
| Wilson's Theorem and Fermat Numbers | |
| |
| |
| |
| Pythagorean Equation | |
| |
| |
| Review Exercises | |
| |
| |
| |
| Arithmetic Functions | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Sigma Function, Tau Function, Dirichlet Product | |
| |
| |
| |
| Dirichlet Inverse, Moebius Function, Euler's Function, Euler's Theorem | |
| |
| |
| An Application to Algebra | |
| |
| |
| Review Exercises | |
| |
| |
| |
| Primitive Roots and Indices | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Primitive Roots: Definition and Properties | |
| |
| |
| |
| Primitive Roots: Existence | |
| |
| |
| |
| Indices | |
| |
| |
| Review Exercises | |
| |
| |
| |
| Quadratic Congruences | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Quadratic Residues and the Legendre Symbol | |
| |
| |
| |
| Gauss' Lemma and the Law of Quadratic Reciprocity | |
| |
| |
| |
| Solution of Quadratic Congruences | |
| |
| |
| Algorithm for Solving Quadratic Congruences | |
| |
| |
| |
| Quadratic Congruences with Composite Moduli | |
| |
| |
| |
| Jacobi Symbol | |
| |
| |
| Review Exercises | |
| |
| |
| |
| Sums of Squares | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Sums of Two Squares | |
| |
| |
| |
| Sums of Four Squares | |
| |
| |
| Review Exercises | |
| |
| |
| |
| Continued Fractions | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Finite Continued Fractions | |
| |
| |
| |
| Infinite Continued Fractions | |
| |
| |
| |
| Approximation by Continued Fractions | |
| |
| |
| |
| Periodic Continued Fractions: I | |
| |
| |
| |
| Periodic Continued Fractions: II | |
| |
| |
| Review Exercises | |
| |
| |
| |
| Nonlinear Diophantine Equations | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Fermat's Last Theorem | |
| |
| |
| Pell's Equation: x[subscript 2] - Dy[subscript 2] = 1 | |
| |
| |
| Mordell's Equation: x[subscript 3] = y[subscript 2] + k | |
| |
| |
| Review Exercises | |
| |
| |
| |
| Computational Number Theory | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Pseudoprimes and Carmichael Numbers | |
| |
| |
| |
| Miller's Test and Strong Pseudoprimes | |
| |
| |
| |
| Factoring: Fermat's Method and the Continued Fraction Method | |
| |
| |
| Trial Division | |
| |
| |
| Fermat's Method | |
| |
| |
| Continued Fraction Method | |
| |
| |
| |
| Quadratic Sieve Method | |
| |
| |
| |
| Pollard p - 1 Method | |
| |
| |
| Review Exercises | |
| |
| |
| |
| Cryptology | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Character Ciphers | |
| |
| |
| |
| Block Ciphers | |
| |
| |
| One-Time Pads: Exponential Ciphers | |
| |
| |
| Public-Key Cryptography | |
| |
| |
| Signatures | |
| |
| |
| Review Exercises | |
| |
| |
| |
| Some Open Questions in Elementary Number Theory | |
| |
| |
| |
| Tables | |
| |
| |
| |
| Answers to Selected Exercises | |
| |
| |
| Bibliography | |
| |
| |
| Index | |