Introduction 1
1 What Is Number Theory? 6
2 Pythagorean Triples 13
3 Pythagorean Triples and the Unit Circle 20
4 Sums of Higher Powers and Fermat's Last Theorem 24
5 Divisibility and the Greatest Common Divisor 28
6 Linear Equations and the Greatest Common Divisor 35
7 Factorization and the Fundamental Theorem of Arithmetic 44
8 Congruences 53
9 Congruences,Powers,and Fermat's Little Theorem 60
10 Congruences,Powers,and Euler's Formula 66
11 Euler's Phi Function and the Chinese Remainder Theorem 70
12 Prime Numbers 78
13 Counting Primes 85
14 Mersenne Primes 91
15 Mersenne Primes and Perfect Numbers 95
16 Powers Modulo m and Successive Squaring 105
17 Computing kth Roots Modulo m 112
18 Powers,Roots,and"Unbreakable"Codes 117
19 Primality Testing and Carmichael Numbers 123
20 Euler's Phi Function and Sums of Divisors 134
21 Powers Modulo p and Primitive Roots 139
22 Primitive Roots and Indices 149
23 Squares Modulo p 156
24 Is-1 a Square Modulo p?Is 2? 164
25 Quadratic Reciprocity 175
26 Which Primes Are Sums of Two Squares? 186
27 Which Numbers Are Sums of Two Squares? 198
28 The Equation X4+Y4=Z4 204
29 Square-Triangular Numbers Revisited 207
30 Pell's Equation 216
31 Diophantine Approximation 222
32 Diophantine Approximation and Pell's Equation 232
33 Number Theory and Imaginary Numbers 239
34 The Gaussian Integers and Unique Factorization 253
35 Irrational Numbers and Transcendental Numbers 270
36 Binomial Coefficients and Pascal's Triangle 286
37 Fibonacci's Rabbits and Linear Recurrence Sequences 297
38 Oh,What a Beautiful Function 310
39 The Topsy-Turvy World of Continued Fractions 324
40 Continued Fractions,Square Roots,and Pell's Equation 340
41 Generating Functions 355
42 Sums of Powers 365
43 Cubic Curves and Elliptic Curves 376
44 Elliptic Curves with Few Rational Points 388
45 Points on Elliptic Curves Modulo p 395
46 Torsion Collections Modulo p and Bad Primes 406
47 Defect Bounds and Modularity Patterns 410
48 Elliptic Curves and Fermat's Last Theorem 416
Further Reading 418
A Factorization of Small Composite Integers 419
B A List of Primes 421
Index 423