| |
| |
| Preface | |
| |
| |
| Structure of the Text | |
| |
| |
| To the Student | |
| |
| |
| To the Instructor | |
| |
| |
| Acknowledgements | |
| |
| |
| Prologue: Number Theory Through the Ages | |
| |
| |
| |
| Numbers, Rational and Irrational (Historical figures: Pythagoras and Hypatia) | |
| |
| |
| |
| Numbers and the Greeks | |
| |
| |
| |
| Numbers You Know | |
| |
| |
| |
| A First Look at Proofs | |
| |
| |
| |
| Irrationality of ?2 | |
| |
| |
| |
| Using Quantifiers | |
| |
| |
| |
| Mathematical Induction (Historical figure: Noether) | |
| |
| |
| |
| The Principle of Mathematical Induction | |
| |
| |
| |
| Strong Induction and the Well-Ordering Principle | |
| |
| |
| |
| The Fibonacci Sequence and the Golden Ratio | |
| |
| |
| |
| The Legend of the Golden Ratio | |
| |
| |
| |
| Divisibility and Primes (Historical figure: Eratosthenes) | |
| |
| |
| |
| Basic Properties of Divisibility | |
| |
| |
| |
| Prime and Composite Numbers | |
| |
| |
| |
| Patterns in the Primes | |
| |
| |
| |
| Common Divisors and Common Multiples | |
| |
| |
| |
| The Division Theorem | |
| |
| |
| |
| Applications of god and 1cm | |
| |
| |
| |
| The Euclidean Algorithm (Historical figure: Euclid) | |
| |
| |
| |
| The Euclidean Algorithm | |
| |
| |
| |
| Finding the Greatest Common Divisor | |
| |
| |
| |
| A Greeker Argument that ?2 Is Irrational | |
| |
| |
| |
| Linear Diophantine Equations (Historical figure: Diophantus) | |
| |
| |
| |
| The Equation aX + bY= 1 | |
| |
| |
| |
| Using the Euclidean Algorithm to Find a Solution | |
| |
| |
| |
| The Diophantine Equation aX + bY = n | |
| |
| |
| |
| Finding All Solutions to a Linear Diophantine Equation | |
| |
| |
| |
| The Fundamental Theorem of Arithmetic (Historical figure: Mersenne) | |
| |
| |
| |
| The Fundamental Theorem | |
| |
| |
| |
| Consequences of the Fundamental Theorem | |
| |
| |
| |
| Modular Arithmetic (Historical figure: Gauss) | |
| |
| |
| |
| Congruence Modulo n | |
| |
| |
| |
| Arithmetic with Congruences | |
| |
| |
| |
| Check-Digit Schemes | |
| |
| |
| |
| The Chinese Remainder Theorem | |
| |
| |
| |
| The Gregorian Calendar | |
| |
| |
| |
| The Mayan Calendar | |
| |
| |
| |
| Modular Number Systems (Historical figure: Turing) | |
| |
| |
| |
| The Number System Z<sub>n</sub>: An Informal View | |
| |
| |
| |
| The Number System Z<sub>n</sub>: Definition and Basic Properties | |
| |
| |
| |
| Multiplicative Inverses in Z<sub>n</sub> | |
| |
| |
| |
| Elementary Cryptography | |
| |
| |
| |
| Encryption Using Modular Multiplication | |
| |
| |
| |
| Exponents Modulo n (Historical figure: Fermat) | |
| |
| |
| |
| Fermat's Little Theorem | |
| |
| |
| |
| Reduced Residues and the Euler ?-Function | |
| |
| |
| |
| Euler's Theorem | |
| |
| |
| |
| Exponentiation Ciphers with a Prime Modulus | |
| |
| |
| |
| The RSA Encryption Algorithm | |
| |
| |
| |
| Primitive Roots (Historical figure: Lagrange) | |
| |
| |
| |
| The Order of an Element of Z<sub>n</sub> | |
| |
| |
| |
| Solving Polynomial Equations in Z<sub>n</sub> | |
| |
| |
| |
| Primitive Roots | |
| |
| |
| |
| Applications of Primitive Roots | |
| |
| |
| |
| Quadratic Residues (Historical figure: Eisenstein) | |
| |
| |
| |
| Squares Modulo n | |
| |
| |
| |
| Euler's Identity and the Quadratic Character of -1 | |
| |
| |
| |
| The Law of Quadratic Reciprocity | |
| |
| |
| |
| Gauss's Lemma | |
| |
| |
| |
| Quadratic Residues and Lattice Points | |
| |
| |
| |
| Proof of Quadratic Reciprocity | |
| |
| |
| |
| Primality Testing (Historical figure: Erd�s) | |
| |
| |
| |
| Primality Testing | |
| |
| |
| |
| Continued Consideration of Charmichael Numbers | |
| |
| |
| |
| The Miller-Rabin Primality Test | |
| |
| |
| |
| Two Special Polynomial Equations in Z<sub>p</sub> | |
| |
| |
| |
| Proof that Miller-Rabin Is Effective | |
| |
| |
| |
| Prime Certificates | |
| |
| |
| |
| The AKS Deterministic Primality Test | |
| |
| |
| |
| Gaussian Integers (Historical figure: Euler) | |
| |
| |
| |
| Definition of the Gaussian Integers | |
| |
| |
| |
| Divisibility and Primes in Z[i] | |
| |
| |
| |
| The Division Theorem for the Gaussian Integers | |
| |
| |
| |
| Unique Factorization in Z[i] | |
| |
| |
| |
| Gaussian Primes | |
| |
| |
| |
| Fermat'sTwo Squares Theorem | |
| |
| |
| |
| Continued Fractions (Historical figure: Ramanujan) | |
| |
| |
| |
| Expressing Rational Numbers as Continued Fractions | |
| |
| |
| |
| Expressing Irrational Numbers as Continued Fractions | |
| |
| |
| |
| Approximating Irrational Numbers Using Continued Fractions | |
| |
| |
| |
| Proving That Convergents are Fantastic Approximations | |
| |
| |
| |
| Some Nonlinear Diophantine Equations (Historical figure: Germain) | |
| |
| |
| |
| Pell's Equation | |
| |
| |
| |
| Fermat's Last Theorem | |
| |
| |
| |
| Proof of Fermat's Last Theorem for n = 4 | |
| |
| |
| |
| Germain's Contributions to Fermat's Last Theorem | |
| |
| |
| |
| A Geometric Look at the Equation x<sup>4</sup> + y<sup>4</sup> = z<sup>2</sup> | |
| |
| |
| Index | |
| |
| |
| Appendix: Axioms to Number Theory (online) | |