Elementary number theory

Description

Chapter 1 Rules of the Game 1 1 . 1 The Integers 1 1.2 Well-Ordering 2 1.3 Induction 6 Exercises 7 Chapter 2 Divisibility 10 2.1 Division 10 2.2 Greatest Common Divisors 22 2.3 The Equation aX bY = c 21 Exercises 30 Chapter *3 Prime Numbers 33 3.1 Primes 33 3.2 A Sieve Method 39 3.3 Fermat Factorization 40 3.4 Some Unsolved Problems 41 Exercises 42 Chapter 4 Congruences 45 4. 1 Congruence 45 4.2 Inverses Modulo m 49 4.3 Fermat’s Little Theorem 53 4.4 Euler’s Theorem 55 4.5 A Historical View 58 4.6 Wilson’s Theorem 60 Exercises 62 Chapter 5 Multiplicative Functions 66 5.1 Three Special Functions 66 5.2 Perfect Numbers 71 5.3 Mobius Inversion 74 Exercises 79 Chapter 0 Solving Congruences 82 6. 1 The Congruence aX = b mod m 83 6.2 Systems of Linear Congruences 85 6.3 The Congruence = a mod m 101 6.4 A General Theorem 111 Exercises 113 Chapter 7 Sums of Squares 119 7.1 Pythagorean Triples 123 7.2 Sums of Two Squares 128 7.3 Sums of Four Squares 134 Exercises 139 Chapter 8 Primitive Roots 143 Exercises 151 Chapter 9 Quadratic Reciprocity 153 9.1 The Legendre Symbol 153 9.2 The Quadratic Reciprocity Theorem 158 Exercises 175 Table of Squares 177 Table of Primes Less Than 10,000 178 Index 191