Elementary Number Theory

Cover......Page 1
Preface......Page 3
What Is Number Theory?......Page 11
1.1. Numbers and Sequences......Page 15
1.2. Sums and Products......Page 26
1.3. Mathematical Induction......Page 33
1.4. The Fibonacci Numbers......Page 40
1.5. Divisibility......Page 46
2.1. Representations of Integers......Page 55
2.2. Computer Operations with Integers......Page 64
2.3. Complexity of Integer Operations......Page 71
3. Primes and Greatest Common Divisors......Page 79
3.1. Prime Numbers......Page 80
3.2. The Distribution of Primes......Page 89
3.3. Greatest Common Divisors and their Properties......Page 103
3.4. The Euclidean Algorithm......Page 112
3.5. The Fundamental Theorem of Arithmetic......Page 122
3.6. Factorization Methods and the Fermat Numbers......Page 137
3.7. Linear Diophantine Equations......Page 147
4.1. Introduction to Congruences......Page 155
4.2. Linear Congruences......Page 167
4.3. The Chinese Remainder Theorem......Page 172
4.4. Solving Polynomial Congruences......Page 181
4.5. Systems of Linear Congruences......Page 188
4.6. Factoring Using the Pollard Rho Method......Page 197
5.1. Divisibility Tests......Page 201
5.2. The Perpetual Calendar......Page 207
5.3. Round-Robin Tournaments......Page 212
5.4. Hashing Functions......Page 214
5.5. Check Digits......Page 219
6.1. Wilson’s Theorem and Fermat’s Little Theorem......Page 227
6.2. Pseudoprimes......Page 235
6.3. Euler’s Theorem......Page 244
7.1. The Euler Phi-Function......Page 249
7.2. The Sum and Number of Divisors......Page 259
7.3. Perfect Numbers and Mersenne Primes......Page 266
7.4. Möbius Inversion......Page 279
7.5. Partitions......Page 287
8.1. Character Ciphers......Page 301
8.2. Block and Stream Ciphers......Page 310
8.3. Exponentiation Ciphers......Page 328
8.4. Public Key Cryptography......Page 331
8.5. Knapsack Ciphers......Page 341
8.6. Cryptographic Protocols and Applications......Page 348
9.1. The Order of an Integer and Primitive Roots......Page 357
9.2. Primitive Roots for Primes......Page 364
9.3. The Existence of Primitive Roots......Page 370
9.4. Discrete Logarithms and Index Arithmetic......Page 378
9.5. Primality Tests Using Orders of Integers and Primitive Roots......Page 388
9.6. Universal Exponents......Page 395
10.1. Pseudorandom Numbers......Page 403
10.2. The ElGamal Cryptosystem......Page 412
10.3. An Application to the Splicing of Telephone Cables......Page 418
11. Quadratic Residues......Page 425
11.1. Quadratic Residues and Nonresidues......Page 426
11.2. The Law of Quadratic Reciprocity......Page 440
11.3. The Jacobi Symbol......Page 453
11.4. Euler Pseudoprimes......Page 463
11.5. Zero-Knowledge Proofs......Page 471
12.1. Decimal Fractions......Page 479
12.2. Finite Continued Fractions......Page 491
12.3. Infinite Continued Fractions......Page 501
12.4. Periodic Continued Fractions......Page 513
12.5. Factoring Using Continued Fractions......Page 527
13. Some Nonlinear Diophantine Equations......Page 531
13.1. Pythagorean Triples......Page 532
13.2. Fermat’s Last Theorem......Page 540
13.3. Sums of Squares......Page 552
13.4. Pell’s Equation......Page 568
13.5. Congruent Numbers......Page 570
14.1. Gaussian Integers and Gaussian Primes......Page 587
14.2. Greatest Common Divisors and Unique Factorization......Page 599
14.3. Gaussian Integers and Sums of Squares......Page 609
Appendix A. Axioms for the Set of Integers......Page 615
Appendix B. Binomial Coefficients......Page 618
C.1. Using Maple for Number Theory......Page 625
C.2. Using Mathematica for Number Theory......Page 629
Appendix D. Number Theory Web Links......Page 634
Appendix E. Tables......Page 636
Answers to Odd-Numbered Exercises......Page 651
Bibliography......Page 731
Index of Biographies......Page 743
Index......Page 745
Photo Credits......Page 762
List of Symbols......Page 763