An Open Door to Number Theory

Cover......Page 1
Title page......Page 4
Contents......Page 8
Preface......Page 12
1. Number systems......Page 14
2. Rings and fields......Page 16
3. Some fundamental facts about \Z and \N......Page 20
4. Proofs by induction......Page 26
5. The binomial theorem......Page 31
6. The fundamental theorem of arithmetic (foreshadowing)......Page 39
7. Divisibility......Page 42
8. Greatest common divisors......Page 44
9. The Euclidean algorithm......Page 46
10. The amazing array......Page 52
11. Convergents......Page 55
12. The amazing super-array......Page 62
13. The modified division algorithm......Page 69
14. Why does the amazing array work?......Page 71
15. Primes......Page 74
16. The proof of the fundamental theorem of arithmetic......Page 77
17. Unique factorization in other rings......Page 81
18. The integers mod , \Z/\Z......Page 84
19. Congruences......Page 89
20. Units and zero-divisors in \Z/\Z......Page 94
21. Cancellation law in \Z/\Z......Page 98
22. Solving linear equations in \Z/\Z......Page 100
23. Solving polynomial equations in \Z/\Z......Page 101
24. Solving systems of linear equations in \Z/\Z......Page 108
25. Lifting roots in \Z/ⁿ\Z......Page 116
26. Wilson’s theorem and its converse......Page 121
27. Calculating ()......Page 123
28. Euler’s and Fermat’s theorems......Page 128
29. The order of an integer modulo ......Page 131
30. Divisibility tests......Page 135
31. Divisibility in \Z[]......Page 140
32. The Euclidean algorithm in \Z[]......Page 143
33. Unique factorization in \Z[]......Page 148
34. The structure of \Z[√2]......Page 151
35. The Euclidean algorithm in \Z[√]......Page 153
36. Factoring in \Z[]......Page 157
37. The primes in \Z[]......Page 162
38. The distribution of primes in \Z......Page 166
39. Perfect squares......Page 170
40. Quadratic residues......Page 173
41. Calculating the Legendre symbol (hard way)......Page 180
42. The arithmetic of \Z[√-2] and the Legendre symbol \Leg{-2}......Page 182
43. Gauss’s lemma......Page 184
44. Calculating the Legendre symbol (easier way)......Page 187
45. The arithmetic of \Z[√-3]......Page 193
46. The arithmetic of \Z[]......Page 195
47. Calculating the Legendre symbol (easiest way)......Page 206
48. The Jacobi symbol......Page 210
49. When \Z/\Z has a primitive root......Page 216
50. Minkowski’s theorem (geometry in the aid of algebra)......Page 221
Appendix A. Tables......Page 236
Appendix B. Projects......Page 246
Bibliography......Page 292
Index......Page 294
Back Cover......Page 297