Solution Manual - Elementary Number Theory and Its Applications 7th Edition by Rosen, (Chapters 1-14)

SOLUTION MANUAL

, Contents

1
Chapter 1. The Integers 1
1.1. Numbers and Sequences 1
1.2. Sums and Products 7
1.3. Mathematical Induction 10
1.4. The Fibonacci Numbers 14
1.5. Divisibility 19

Chapter 2. Integer Representations and Operations 25
2.1. Representations of Integers 25
2.2. Computer Operations with Integers 29
2.3. Complexity and Integer Operations 31

Chapter 3. Primes and Greatest Common Divisors 35
3.1. Prime Numbers 35
3.2. The Distribution of Primes 38
3.3. Greatest Common Divisors and their Properties 44
3.4. The Euclidean Algorithm 49
3.5. The Fundamental Theorem of Arithmetic 53
3.6. Factorization Methods and the Fermat Numbers 63
3.7. Linear Diophantine Equations 66

Chapter 4. Congruences 71
4.1. Introduction to Congruences 71
4.2. Linear Congruences 78
4.3. The Chinese Remainder Theorem 82
4.4. Solving Polynomial Congruences 86
4.5. Systems of Linear Congruences 89
4.6. Factoring Using the Pollard Rho Method 91

Chapter 5. Applications of Congruences 93
5.1. Divisibility Tests 93
5.2. The Perpetual Calendar 98
5.3. Round-Robin Tournaments 101
5.4. Hashing Functions 103
5.5. Check Digits 104

Chapter 6. Some Special Congruences 111
6.1. Wilson’s Theorem and Fermat’s Little Theorem 111
6.2. Pseudoprimes 115
6.3. Euler’s Theorem 117

Chapter 7. Multiplicative Functions 121
7.1. The Euler Phi-Function 121
7.2. The Sum and Number of Divisors 127
7.3. Perfect Numbers and Mersenne Primes 133
7.4. Mobius Inversion 137
7.5. Partitions 141
1

,2

Chapter 8. Cryptology 151
8.1. Character Ciphers 151
8.2. Block and Stream Ciphers 152
8.3. Exponentiation Ciphers 158
8.4. Public Key Cryptography 159
8.5. Knapsack Ciphers 161
8.6. Cryptographic Protocols and Applications 162

Chapter 9. Primitive Roots 165
9.1. The Order of an Integer and Primitive Roots 165
9.2. Primitive Roots for Primes 168
9.3. The Existence of Primitive Roots 171
9.4. Discrete Logarithms and Index Arithmetic 173
9.5. Primality Tests Using Orders of Integers and Primitive Roots 176
9.6. Universal Exponents 178

Chapter 10. Applications of Primitive Roots and the Order of an Integer 181
10.1. Pseudorandom Numbers 181
10.2. The ElGamal Cryptosystem 183
10.3. An Application to the Splicing of Telephone Cables 184

Chapter 11. Quadratic Residues 187
11.1. Quadratic Residues and Nonresidues 187
11.2. The Law of Quadratic Reciprocity 194
11.3. The Jacobi Symbol 199
11.4. Euler Pseudoprimes 202
11.5. Zero-Knowledge Proofs 203

Chapter 12. Decimal Fractions and ContinuedFractions 205
12.1. Decimal Fractions 205
12.2. Finite Continued Fractions 208
12.3. Infinite Continued Fractions 212
12.4. Periodic Continued Fractions 214
12.5. Factoring Using Continued Fractions 218

Chapter 13. Some Nonlinear Diophantine Equations 221
13.1. Pythagorean Triples 221
13.2. Fermat’s Last Theorem 224
13.3. Sums of Squares 227
13.4. Pell’s Equation 230
13.5. Congruent Numbers 231

Chapter 14. The Gaussian Integers 239
14.1. Gaussian Integers and Gaussian Primes 239
14.2. Greatest Common Divisors and Unique Factorization 247
14.3. Gaussian Integers and Sums of Squares 256

Appendix A. Axioms for the Set of Integers 261

Appendix B. Binomial Coefficients 263

, CHAPTER 1


The Integers

1.1. Numbers and Sequences

1.1.1. a. The set of integers greater than 3 is well-ordered. Every subset of this set is also a subset of the set
of positive integers, and hence must have a least element.

b. The set of even positive integers is well-ordered. Every subset of this set is also a subset of the set
of positive integers, and hence must have a least element.

c. The set of positive rational numbers is not well-ordered. This set does not have a least element.
If a/b were the least positive rational number then a/(b + a) would be a smaller positive rational
number, which is a contradiction.

d. The set of positive rational numbers of the form a/2 is well-ordered. Consider a subset of numbers
of this form. The set of numerators of the numbers in this subset is a subset of the set of positive
integers, so it must have a least element b. Then b/2 is the least element of the subset.

e. The set of nonnegative rational numbers is not well-ordered. The set of positive rational numbers
is a subset with no least element, as shown in part c.

1.1.2. Let S be the set of all positive integers of the form a - bk. S is not empty because a - b(-1) = a + b
is a positive integer. Then the well-ordering principle implies that S has a least element, which is the
number we’re looking for.

1.1.3. Suppose that x and y are rational numbers. Then x = a/b and y = c/d, where a, b, c, and d are integers
with b = 0 and d = 0. Then xy = (a/b) • (c/d) = ac/bd and x + y = a/b + c/d = (ad + be)/bd where bd =
0. Because both x + y and xy are ratios of integers, they are both rational.

1.1.4. a. Suppose that x is rational and y is irrational. Then there exist integers a and b such that x = a where
a and b are integers with b =0. Suppose that x + y is rational. Then there exist integers c and d with
d = 0 such that x + y = d. This implies that y = (x + y) — x = (a/b) — (c/d) = (ad — be)/bd, which
means that y is rational, a contradiction. Hence x + y is irrational.

b. This is false. A counterexample is given by a/2 + (— a/2) = 0.

c. This is false. A counterexample is given by 0 • -\/2 = 0.

d. This is false. A counterexample is given by \/2 • a/2 = 2.

1.1.5. Suppose that V3 were rational. Then there would exist positive integers a and b with y^ = a/b. Con­
sequently, the set S = {k V3 | k and ^/3 are positive integers} is nonempty because a = b^/S. Therefore,
by the well-ordering property, S has a smallest element, say s = ^/3. We have ^/3 — s = s^/3 — ^/3 =
(s — t)\/3. Because sV3 = 31 and s are both integers, sV3 — s = (s — t)yz3 must also be an integer. Fur­
thermore, it is positive, because ^/3 — s = s( /3 — 1) and v/3 > 1. It is less than s because s = ^/3,
a



sV3 = 31, and Vd < 3. This contradicts the choice of s as the smallest positive integer in S. It follows
that \/3 is irrational.


1