An Introduction To The Theory Of Numbers (merrill Mathematics Series)

[Cover text] THIS INTRODUCTION TO THE THEORY OF NUMBERS PLACES SPECIAL EMPHASIS ON BASIC CONCEPTS AND VARIETY OF TREATMENT THROUGHOUT. Its variety of approaches and methods is designed to show the richness of the theory of numbers. The author emphasizes that theory can not be fully understood until it can be effectively applied. Accordingly, the book provides more than the usual number at exercises and problems. Detailed exposition in the early chapters, especially in the first three, also aids understanding. The book includes many illustrative examples worked out in detail to reinforce the theory presented. It frequently gives several alternative methods of proof. A series of Notes on each chapter covers (1) reference to additional material, (2) detailed proofs by mathematical induction, and (3) discussion of interesting sidelights. RALPH G. AHCHIBALD (Ph. D, University of Chicago) is Professor of Mathematics at Queens College of the City University of New York. He has published a number of papers in mathematical journals in the United States and Canada. 1 Introduction 1-1 Nature of the Subject 1 1-2 Some Questions Considered 1 -3 Problems 5 2 Divisibility 2-1 Introduction 7 2-2 Sundry Definitions 8 2-3 Elementary Theorems 8 2-4 Some Fundamental Principles 2-5 Basic Theorem 10 2-6 Mathematical Induction 11 2-7 Problems 13 2-8 Scales of Notation 14 2-9 Problems 15 2-10 Common Divisors 16 2-11 Euclid’s Algorithm 18 2-12 Linear Diophantine Equations 19 2-13 Problems 21 2-14 Greatest Common Divisor and Least Common Multiple 2-15 Number of Primes Infinite 24 2-16 Sieve of Eratosthenes 26 2-17 Unique Factorization 26 2-18 Problems 28 3 Congruences 3-1 Residue Classes 29 3-2 Congruence Symbol 30 3-3 Properties of Congruences 30 3-4 Problems 34 3-5 Euler’s 0-Function 35 % 3-6 Fermat’s Theorem and Euler’s Generalization 3-7 Pseudoprimes 41 3-8 Problems 42 3-9 Linear Congruences and Their Solution 43 3-10 Simple Continued Fractions 44 3-11 Wilson’s Theorem 48 3-12 The Chinese Remainder Theorem 48 3-13 Problems 51 3-14 Identical and Conditional Congruences 52 3-15 Equivalent Congruences 53 3-16 Division of Polynomials, modulo m 54 3-17 Problems 56 3-18 Number of Solutions of a Congruence 57 3-19 Number of Solutions of Special Congruences 3-20 Number of Solutions of a Binomial Quadratic Congruence 61 3-21 Problems 63 3-22 Solution of the Congruence f(x ) = 0 (mod m) 3-23 Polynomials Representing Primes 68 3-24 Problems 70 4 Some Significant Functions in the Theory of Numbers 4-1 The Greatest Integer Function 71 4-2 Problems 77 4-3 Generalization of Euler’s 0-Function 78 4-4 Functions t(/j) and o{n) 81 4-5 Problems 84 4-6 Perfect Numbers 85 4-7 Mobius //-Function 86 4-8 Liouville’s Function X(n) 91 4- 9 Problems 93 4-10 Recurrence Formulae 95 4-11 Fibonacci’s and Lucas’Sequences 99 4-12 Problems 99 5 Primitive Roots and Indices 5- 1 Belonging to an Exponent 103 5-2 Problems 109 5-3 Primitive Roots 110 5-4 Obtaining Primitive Roots 113 5-5 Sum of Numbers Belonging to an Exponent 115 5-6 Further Consideration of Primitive Roots of p n 1 5-7 Problems 120 5-8 Indices 122 5-9 Problems 126 6 Quadratic Congruences 6-1 A Quadratic Congruence 129 6-2 Quadratic Residue and Quadratic Nonresidue 130 6-3 Problems 132 6-4 Euler’s Criterion 132 6-5 Legendre’s Symbol 134 6-6 Quadratic Reciprocity Law 134 6-7 Problems 142 6-8 Another Proof of the Quadratic Reciprocity Law 6-9 The Jacobi Symbol 147 6-10 Generalized Quadratic Reciprocity Law 150 6-11 Problems 151 7 E l e m e n t a r y Considerations on the Distribution of Primes and Composites 7-1 Introduction 153 7-2 The O-notation 154 7-3 Problems 156 7-4 Bertrand’s Postulate 157 7-5 Problems 162 7-6 Bounds for n(x) 163 7-7 Remarks on the Prime Number Theorem 168 7-8 Primes in Arithmetical Progressions 169 7-9 Highly Composite Numbers 170 7-10 Relatively Highly Composite Numbers 172 7-11 Problems 173 8 C o n tinued Fractions 8-1 Introduction 175 8-2 Finite Continued Fractions 177 8-3 Convergents and Their Limits 179 8-4 Problems 184 ' 8-5 Representation of Irrational Numbers 184 8-6 Approximation by Rational Numbers 189 8-7 Problems 196 8-8 Quadratic Irrational Numbers 197 8-9 Periodic Continued Fractions 201 8-10 Problems 209 8-11 Pell’s Equation 209 8-12 Problems 217 8-13 Farey Sequences 218 8-14 Problems 221 9 C e r tain Diophantine Equations and Sums of Squares 9-1 Introductory Remarks 223 9-2 The Pythagorean Equation 224 9-3 The Diophantine Equation x 2 + 2 y 1 — z 2 225 9-4 Problems 228 9-5 Some Fourth Degree Diophantine Equations 228 9-6 Problems 237 9-7 Solution of the Equations X 4 — 2 Y 4 — ± Z 2 9-8 Sum of Two Squares 244 9-9 Sum of Three Squares 247 9-10 Problems 249 9-11 Sum of Four Squares 250 9-12 Remarks on Waring’s Problem 252 9-13 Problems 253 Notes 255 Bibliography 288 Table of Primes 291