An introduction to the theory of numbers

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