Chapter 1:Arithmetic of the Integers.................. 1
1.1 Introduction---Where We Begin and Why............. 1
1.2 The Fundamental Laws.............................. 7
1.3 Divisibility...................................... 33
1.4 Prime Numbers..................................... 42
1.5 Computer Arithmetic and Complexity................ 52
1.6 Applications to a Set of Quadratics............... 65
Chapter 2 Congruences................................ 75
2.1 The Basics........................................ 75
2.2 Linear Congruences................................ 83
2.3 Arithmetic Functions---Euler's Totient............ 89
2.4 The Chinese Remainder Theorem..................... 99
2.5 Polynomial Congruences & Thue's Theorem........... 103
2.6 Cryptography and Factoring....................... 118
2.7 Quadratic Polynomials............................ 136
Chapter 3 Primitive Roots............................ 145
3.1 Order............................................. 145
3.2 Existence......................................... 150
3.3 Indices........................................... 154
3.4 Primality Testing and Cryptography................ 160
3.5 Quadratic Orders, Ideals and Units................ 176
Chapter 4 Quadratic Residues......................... 185
4.1 The Quadratic Reciprocity Law..................... 185
4.2 The Jacobi and Kronecker Symbols.................. 196
4.3 Quadratic Polynomials and Primes.................. 203
4.4 Quadratic Residues & Primality Testing............ 209
4.5 Applications to Quadratic Orders.................. 212
Chapter 5 Continued Fractions........................ 221
5.1 Finite Continued Fractions........................ 221
5.2 Infinite continued Fractions...................... 228
5.3 Periodic Continued Fractions...................... 238
5.4 Continued Fractions and Factoring................. 254
5.5 The Continued Fraction Algorithm.................. 257
Chapter 6 Diophantine Equations...................... 273
6.1 Sums of Squares................................... 273
6.2 The Equation x^2-Dy^2=n........................... 294
6.3 Diophantine Equations of Higher Degree............ 308
6.4 Elliptic Curves, Factoring, and Primality......... 310
6.5 Applications: Algebraic Number Theory............ 321
Appendices............................................ 361
Appendix A: Set Theory............................... 362
Appendix B: Primes < 9547 & Least Primitive Root.... 368
Appendix C: Tables of Special Primes................. 373
Appendix D: Cunningham Factorizations................ 375
Appendix E: Pseudoprimes & Carmichael Numbers........ 376
Appendix F: Indices.................................. 377
Appendix G: Values of Some Arithmetic Functions....... 378
Appendix H: The ABC Conjecture....................... 379
Appendix I: The Prime Number Theorem................. 380
Solutions to Odd Numbered Exercises................... 381
Bibliography.......................................... 423
List of Symbols....................................... 426
Index................................................. 427
Last updated: September 10, 2003