Preface |
|
xi | |
|
|
1 | (12) |
|
1.1 What is number theory? |
|
|
1 | (3) |
|
|
4 | (3) |
|
1.3 Mathematical induction |
|
|
7 | (5) |
|
|
12 | (1) |
|
|
12 | (1) |
|
|
13 | (10) |
|
2.1 Basic definitions and properties |
|
|
13 | (2) |
|
2.2 The division algorithm |
|
|
15 | (2) |
|
2.3 Representations of integers |
|
|
17 | (6) |
|
3 Greatest Common Divisor |
|
|
23 | (22) |
|
3.1 Greatest common divisor |
|
|
23 | (5) |
|
3.2 The Euclidean algorithm |
|
|
28 | (4) |
|
3.3 Linear Diophantine equations |
|
|
32 | (9) |
|
|
41 | (4) |
|
|
41 | (1) |
|
The number of steps in the Euclidean algorithm |
|
|
41 | (2) |
|
Geometric interpretation of the equation ax + by = c |
|
|
43 | (2) |
|
|
45 | (16) |
|
4.1 The sieve of Eratosthenes |
|
|
45 | (4) |
|
4.2 The fundamental theorem of arithmetic |
|
|
49 | (5) |
|
4.3 Distribution of prime numbers |
|
|
54 | (4) |
|
|
58 | (3) |
|
|
58 | (1) |
|
Nonunique factorization and Fermat's Last Theorem |
|
|
58 | (3) |
|
|
61 | (18) |
|
|
61 | (4) |
|
|
65 | (5) |
|
5.3 Application: Check digits and the ISBN-10 system |
|
|
70 | (3) |
|
5.4 The Chinese remainder theorem |
|
|
73 | (6) |
|
|
79 | (14) |
|
|
80 | (4) |
|
|
84 | (5) |
|
|
89 | (3) |
|
|
92 | (1) |
|
|
92 | (1) |
|
|
93 | (18) |
|
7.1 Order of an element mod n |
|
|
93 | (3) |
|
7.2 Existence of primitive roots |
|
|
96 | (4) |
|
7.3 Primitive roots modulo composites |
|
|
100 | (3) |
|
7.4 Application: Construction of the regular 17-gon |
|
|
103 | (5) |
|
|
108 | (3) |
|
|
108 | (1) |
|
Straightedge and compass constructions |
|
|
109 | (2) |
|
|
111 | (20) |
|
8.1 Monoalphabetic substitution ciphers |
|
|
111 | (5) |
|
8.2 The Pohlig--Hellman cipher |
|
|
116 | (5) |
|
8.3 The Massey--Omura exchange |
|
|
121 | (4) |
|
|
125 | (4) |
|
|
129 | (2) |
|
|
129 | (1) |
|
|
130 | (1) |
|
|
131 | (18) |
|
9.1 Quadratic congruences |
|
|
131 | (2) |
|
9.2 Quadratic residues and nonresidues |
|
|
133 | (4) |
|
9.3 Quadratic reciprocity |
|
|
137 | (7) |
|
|
144 | (4) |
|
|
148 | (1) |
|
|
148 | (1) |
|
10 Applications of Quadratic Residues |
|
|
149 | (12) |
|
10.1 Application: Construction of tournaments |
|
|
149 | (5) |
|
10.2 Consecutive quadratic residues and nonresidues |
|
|
154 | (2) |
|
10.3 Application: Hadamard matrices |
|
|
156 | (5) |
|
|
161 | (22) |
|
|
161 | (4) |
|
|
165 | (6) |
|
11.3 Factorization of Gaussian integers |
|
|
171 | (5) |
|
11.4 Lagrange's four squares theorem |
|
|
176 | (5) |
|
|
181 | (2) |
|
|
181 | (2) |
|
12 Further Topics in Diophantine Equations |
|
|
183 | (20) |
|
12.1 The case n = 4 in Fermat's Last Theorem |
|
|
183 | (3) |
|
|
186 | (8) |
|
|
194 | (5) |
|
|
199 | (4) |
|
|
199 | (1) |
|
|
200 | (3) |
|
|
203 | (32) |
|
13.1 Finite continued fractions |
|
|
204 | (8) |
|
13.2 Infinite continued fractions |
|
|
212 | (7) |
|
13.3 Rational approximation of real numbers |
|
|
219 | (13) |
|
|
232 | (3) |
|
Continued fraction expansion of e |
|
|
232 | (1) |
|
Continued fraction expansion of tan x |
|
|
232 | (1) |
|
|
233 | (2) |
|
14 Continued Fraction Expansions of Quadratic Irrationals |
|
|
235 | (28) |
|
14.1 Periodic continued fractions |
|
|
235 | (13) |
|
14.2 Continued fraction factorization |
|
|
248 | (6) |
|
14.3 Continued fraction solution of Pell's equation |
|
|
254 | (6) |
|
|
260 | (3) |
|
Three squares and triangular numbers |
|
|
260 | (2) |
|
History of Pell's equation |
|
|
262 | (1) |
|
|
263 | (40) |
|
|
263 | (7) |
|
15.2 The group of arithmetic functions |
|
|
270 | (8) |
|
|
278 | (5) |
|
15.4 Application: Cyclotomic polynomials |
|
|
283 | (4) |
|
15.5 Partitions of an integer |
|
|
287 | (12) |
|
|
299 | (4) |
|
The lore of perfect numbers |
|
|
299 | (1) |
|
Pioneers of integer partitions |
|
|
300 | (3) |
|
|
303 | (16) |
|
|
303 | (6) |
|
|
309 | (3) |
|
|
312 | (3) |
|
16.4 Finding large primes |
|
|
315 | (4) |
|
17 Analytic Number Theory |
|
|
319 | (36) |
|
17.1 Sum of reciprocals of primes |
|
|
319 | (3) |
|
17.2 Orders of growth of functions |
|
|
322 | (2) |
|
|
324 | (7) |
|
17.4 Bertrand's postulate |
|
|
331 | (4) |
|
17.5 The prime number theorem |
|
|
335 | (6) |
|
17.6 The zeta function and the Riemann hypothesis |
|
|
341 | (5) |
|
|
346 | (6) |
|
|
352 | (3) |
|
|
352 | (3) |
|
|
355 | (42) |
|
|
355 | (3) |
|
18.2 Intersections of lines and curves |
|
|
358 | (9) |
|
18.3 The group law and addition formulas |
|
|
367 | (5) |
|
|
372 | (3) |
|
18.5 Elliptic curves mod p |
|
|
375 | (3) |
|
18.6 Encryption via elliptic curves |
|
|
378 | (3) |
|
18.7 Elliptic curve method of factorization |
|
|
381 | (5) |
|
18.8 Fermat's Last Theorem |
|
|
386 | (4) |
|
|
390 | (7) |
|
|
390 | (3) |
|
Associativity of the group law |
|
|
393 | (4) |
A Web Resources |
|
397 | (4) |
B Notation |
|
401 | (4) |
References |
|
405 | (4) |
Index |
|
409 | |