Elementary Number Theory

Title Preface Contents 1. Rules of the Game 1.1 The Integers 1.2 Well-Ordering 1.3 Induction Exercises 2. Divisibility 2.1 Division 2.2 Greatest Common Divisors 2.3 The Equation aX + bY = c Exercises 3. Prime Numbers 3.1 Primes 3.2 A Sieve Method 3.3 Fermat Factorization 3.4 Some Unsolved Problems Exercises 4. Congruences 4.1 Congruence 4.2 Inverses Modulo m 4.3 Fermat’s Little Theorem 4.4 Euler’s Theorem 4.5 A Historical View 4.6 Wilson’s Theorem Exercises 5. Multiplicative Functions 5.1 Three Special Functions 5.2 Perfect Numbers 5.3 Möbius Inversion Exercises 6. Solving Congruences 6.1 The Congruence aX equiv b mod m 6.2 Systems of Linear Congruences 6.3 The Congruence X^2 equiv a mod m 6.4 A General Theorem Exercises 7. Sums of Squares 7.1 Pythagorean Triples 7.2 Sums of Two Squares 7.3 Sums of Four Squares Exercises 8. Primitive Roots Exercises 9. Quadratic Reciprocity 9.1 The Legendre Symbol 9.2 The Quadratic Reciprocity Theorem Exercises Tables Index