Elementary Number Theory and Its Applications, 5th edition, Instructor's Solutions Manual

Description

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