Student Solutions Manual for Elementary Number Theory

front page......Page 1
1.1. Numbers, Sequences, and Sums......Page 3
1.2. Sums and Products......Page 9
1.3. Mathematical Induction......Page 12
1.4. The Fibonacci Numbers......Page 16
1.5. Divisibility......Page 21
2.1. Representations of Integers......Page 27
2.2. Computer Operations with Integers......Page 31
2.3. Complexity and Integer Operations......Page 33
3.1. Prime Numbers......Page 37
3.2. The Distribution of Primes......Page 40
3.3. Greatest Common Divisors......Page 45
3.4. The Euclidean Algorithm......Page 49
3.5. The Fundamental Theorem of Arithmetic......Page 54
3.6. Factorization Methods and the Fermat Numbers......Page 63
3.7. Linear Diophantine Equations......Page 66
4.1. Introduction to Congruences......Page 71
4.2. Linear Congruences......Page 77
4.3. The Chinese Remainder Theorem......Page 81
4.4. Solving Polynomial Congruences......Page 85
4.5. Systems of Linear Congruences......Page 88
4.6. Factoring Using the Pollard Rho Method......Page 90
5.1. Divisibility Tests......Page 93
5.2. The Perpetual Calendar......Page 96
5.3. Round-Robin Tournaments......Page 99
5.4. Hashing Functions......Page 101
5.5. Check Digits......Page 102
6.1. Wilson’s Theorem and Fermat’s Little Theorem......Page 107
6.2. Pseudoprimes......Page 110
6.3. Euler’s Theorem......Page 113
7.1. The Euler Phi-Function......Page 115
7.2. The Sum and Number of Divisors......Page 121
7.3. Perfect Numbers and Mersenne Primes......Page 127
7.4. M¨obius Inversion......Page 131
8.1. Character Ciphers......Page 135
8.2. Block and Stream Ciphers......Page 136
8.3. Exponentiation Ciphers......Page 142
8.4. Public Key Cryptography......Page 143
8.5. Knapsack Ciphers......Page 144
8.6. Cryptographic Protocols and Applications......Page 146
9.1. The Order of an Integer and Primitive Roots......Page 149
9.2. Primitive Roots for Primes......Page 151
9.3. The Existence of Primitive Roots......Page 154
9.4. Index Arithmetic......Page 156
9.5. Primality Tests Using Orders of Integers and Primitive Roots......Page 160
9.6. Universal Exponents......Page 161
10.1. Pseudorandom Numbers......Page 165
10.2. The ElGamal Cryptosystem......Page 167
10.3. An Application to the Splicing of Telephone Cables......Page 168
11.1. Quadratic Residues and Nonresidues......Page 171
11.2. The Law of Quadratic Reciprocity......Page 177
11.3. The Jacobi Symbol......Page 182
11.4. Euler Pseudoprimes......Page 186
11.5. Zero-Knowledge Proofs......Page 187
12.1. Decimal Fractions......Page 189
12.2. Finite Continued Fractions......Page 192
12.3. Infinite Continued Fractions......Page 196
12.4. Periodic Continued Fractions......Page 198
12.5. Factoring Using Continued Fractions......Page 202
13.1. Pythagorean Triples......Page 205
13.2. Fermat’s Last Theorem......Page 206
13.3. Sums of Squares......Page 211
13.4. Pell’s Equation......Page 213
14.1. Gaussian Integers and Gaussian Primes......Page 217
14.2. Greatest Common Divisors and Unique Factorization......Page 225
14.3. Gaussian Integers and Sums of Squares......Page 234
APPENDIX A......Page 237
APPENDIX B......Page 239