Preface |
|
ix | |
|
1 Divisibility in the Integers Z |
|
|
1 | (14) |
|
|
1 | (1) |
|
|
1 | (1) |
|
1.3 The Division Algorithm |
|
|
2 | (1) |
|
1.4 Greatest Common Divisors |
|
|
3 | (1) |
|
1.5 The Euclidean Algorithm |
|
|
3 | (3) |
|
|
6 | (1) |
|
|
7 | (3) |
|
1.8 Supplementary Problems |
|
|
10 | (5) |
|
2 Prime Numbers and Factorization |
|
|
15 | (14) |
|
|
15 | (1) |
|
|
16 | (1) |
|
2.3 [ Listing Primes: The Sieve of Eratosthenes |
|
|
16 | (2) |
|
2.4 Unique Factorization of Integers into Primes |
|
|
18 | (3) |
|
2.5 The Difficulty of Factorization |
|
|
21 | (1) |
|
2.6 Using Factorization to Compute a GCD |
|
|
21 | (1) |
|
|
22 | (1) |
|
|
23 | (3) |
|
2.9 Supplementary Problems |
|
|
26 | (3) |
|
3 Congruences and the Sets Zn |
|
|
29 | (16) |
|
|
29 | (1) |
|
3.2 Definition and Examples of Congruences |
|
|
29 | (1) |
|
|
30 | (1) |
|
3.4 Addition and Multiplication Tables for Zn |
|
|
31 | (1) |
|
3.5 Properties of Congruences |
|
|
32 | (2) |
|
|
34 | (3) |
|
|
37 | (1) |
|
|
38 | (3) |
|
3.9 Supplementary Problems |
|
|
41 | (4) |
|
|
45 | (16) |
|
|
45 | (1) |
|
4.2 Solving a Single Linear Congruence |
|
|
45 | (4) |
|
4.3 Solving Systems of Two or More Congruences |
|
|
49 | (4) |
|
|
53 | (1) |
|
|
54 | (4) |
|
4.6 Supplemental Problems |
|
|
58 | (3) |
|
5 The Theorems of Fermat and Euler |
|
|
61 | (18) |
|
|
61 | (1) |
|
5.2 Fermat's Theorem for Prime Moduli |
|
|
61 | (3) |
|
5.3 Euler's Function and Euler's Theorem |
|
|
64 | (5) |
|
|
69 | (2) |
|
|
71 | (1) |
|
|
71 | (4) |
|
5.7 Supplementary Problems |
|
|
75 | (4) |
|
6 Applications to Modern Cryptography |
|
|
79 | (20) |
|
|
79 | (1) |
|
6.2 The Basics of Encryption |
|
|
80 | (1) |
|
6.3 Primitive Roots in Zp |
|
|
81 | (1) |
|
6.4 Diffie-Hellman Key Exchange |
|
|
82 | (3) |
|
6.5 Public Key Cryptography and the RSA System |
|
|
85 | (4) |
|
6.6 Security versus Authenticity |
|
|
89 | (2) |
|
|
91 | (1) |
|
|
92 | (3) |
|
6.9 Supplemental Problems |
|
|
95 | (4) |
|
7 Quadratic Residues and Quadratic Reciprocity |
|
|
99 | (20) |
|
|
99 | (1) |
|
7.2 Quadratic Residues and the Legendre Symbol |
|
|
99 | (3) |
|
7.3 Computing the Legendre Symbol |
|
|
102 | (3) |
|
7.4 Quadratic Reciprocity |
|
|
105 | (3) |
|
7.5 Composite Moduli and the Jacobi Symbol |
|
|
108 | (2) |
|
|
110 | (1) |
|
|
111 | (5) |
|
7.8 Supplementary Problems |
|
|
116 | (3) |
|
8 Some Fundamental Number Theory Functions |
|
|
119 | (20) |
|
|
119 | (1) |
|
8.2 The Greatest Integer Function |
|
|
119 | (4) |
|
8.3 The Functions τ(η), σ(η), σκ(η) |
|
|
123 | (4) |
|
8.4 The Mobius Inversion Formula |
|
|
127 | (3) |
|
|
130 | (1) |
|
|
131 | (4) |
|
8.7 Supplementary Problems |
|
|
135 | (4) |
|
|
139 | (26) |
|
|
139 | (1) |
|
9.2 The Linear Equation ax + by = c |
|
|
139 | (3) |
|
9.3 The Equation x2 + y2 = z2 |
|
|
142 | (3) |
|
9.4 The Equation x4 + y4 = z4 |
|
|
145 | (3) |
|
9.5 The Equation xn + yn = zn, n < 2 |
|
|
148 | (1) |
|
|
149 | (7) |
|
|
156 | (1) |
|
|
157 | (1) |
|
|
158 | (3) |
|
9.10 Supplementary Problems |
|
|
161 | (4) |
|
|
165 | (32) |
|
|
165 | (1) |
|
10.2 The Finite Fields Fpn |
|
|
166 | (1) |
|
10.3 The Order of a Finite Field |
|
|
167 | (3) |
|
10.4 Constructing Finite Fields |
|
|
170 | (4) |
|
10.5 The Multiplicative Structure of Fq |
|
|
174 | (3) |
|
10.6 The Subfields of Fpn |
|
|
177 | (2) |
|
10.7 Counting Irreducible Polynomials over Fpn |
|
|
179 | (4) |
|
10.8 Lagrange Interpolation Formula |
|
|
183 | (2) |
|
10.9 An Application to Latin and Sudoku Squares |
|
|
185 | (4) |
|
|
189 | (1) |
|
|
190 | (4) |
|
10.12 Supplementary Problems |
|
|
194 | (3) |
|
11 Some Open Problems in Number Theory |
|
|
197 | (20) |
|
|
197 | (1) |
|
|
198 | (13) |
|
|
211 | (1) |
|
|
211 | (6) |
A Mathematical Induction |
|
217 | (8) |
B Sets of Numbers Beyond the Integers |
|
225 | (12) |
Bibliography |
|
237 | (2) |
Index |
|
239 | |