| |
| |
| Preface | |
| |
| |
| Logical dependence of chapters | |
| |
| |
| |
| The Fundamental Theorem, Greatest Common Divisors and Least Common Multiples | |
| |
| |
| |
| Primes and the fundamental theorem | |
| |
| |
| |
| Greatest common divisor and least common multiple | |
| |
| |
| |
| Euclid's algorithm for the gcd | |
| |
| |
| |
| [x] and applications | |
| |
| |
| |
| Further projects | |
| |
| |
| |
| Listing Primes | |
| |
| |
| |
| Primes by division | |
| |
| |
| |
| Primes by multiplication (elimination of composites) | |
| |
| |
| |
| Approximations to [pi](x) | |
| |
| |
| |
| The sieve of Eratosthenes | |
| |
| |
| |
| Congruences | |
| |
| |
| |
| Congruences: basic properties | |
| |
| |
| |
| Inverses mod m and solutions of certain congruences | |
| |
| |
| |
| Further examples of congruences | |
| |
| |
| |
| Powers and Pseudoprimes | |
| |
| |
| |
| Fermat's (little) theorem | |
| |
| |
| |
| The power algorithm | |
| |
| |
| |
| Head's algorithm for multiplication mod m | |
| |
| |
| |
| Pseudoprimes | |
| |
| |
| |
| Wilson's theorem | |
| |
| |
| |
| Miller's Test and Strong Pseudoprimes | |
| |
| |
| |
| Miller's test | |
| |
| |
| |
| Probabilistic primality testing | |
| |
| |
| |
| Euler's Theorem, Orders and Primality Testing | |
| |
| |
| |
| Euler's function (the [phis]-function or totient function) | |
| |
| |
| |
| Euler's theorem and the concept of order | |
| |
| |
| |
| Primality tests | |
| |
| |
| |
| Periods of decimals | |
| |
| |
| |
| Cryptography | |
| |
| |
| |
| Exponentiation ciphers | |
| |
| |
| |
| Public key cryptography: RSA ciphers | |
| |
| |
| |
| Coin-tossing by telephone | |
| |
| |
| |
| Primitive Roots | |
| |
| |
| |
| Properties and applications of primitive roots | |
| |
| |
| |
| Existence and nonexistence of primitive roots | |
| |
| |
| |
| The Number of Divisors d and the Sum of Divisors [sigma] | |
| |
| |
| |
| The function d(n) | |
| |
| |
| |
| Multiplicative functions and the sum function [sigma](n) | |
| |
| |
| |
| Tests for primality of the Mersenne numbers 2[superscript m] - 1 | |
| |
| |
| |
| Continued Fractions and Factoring | |
| |
| |
| |
| Continued fractions: initial ideas and definitions | |
| |
| |
| |
| The continued fraction for [square root]n | |
| |
| |
| |
| Proofs of some properties of continued fractions | |
| |
| |
| |
| Pell's equation | |
| |
| |
| |
| The continued fraction factoring method | |
| |
| |
| |
| Quadratic Residues | |
| |
| |
| |
| Definitions and examples | |
| |
| |
| |
| The quadratic character of 2 | |
| |
| |
| |
| Quadratic reciprocity | |
| |
| |
| |
| The Jacobi symbol and a program for finding (n/p) | |
| |
| |
| |
| Solving the equation x[superscript 2] [identical with] a (mod p): quadratic congruences | |
| |
| |
| Bibliography | |
| |
| |
| Index | |
| |
| |
| Index of Listed Programs | |
| |
| |
| Index of Notation | |