K23541_SM_Cover.indd 1 11/18/14 7:13 PM 2 First Course in Abstract Algebra Rings Groups and Fields 3rd Edition Anderson Solutions Manual 3 Chapter 1 — The Natural Numbers 1. This is obvious if n = 1. Assume the theorem is true for integers less than n. Given the equation 1 + 2 + · · · + (n − 1) = (n − 1)n, add the next term n to both sides. Elementary algebra gives (n − 1)n + n = n(n + 1) , 2 2 showing that the theorem is true for n. The theorem follows by the principle of math - ematical induction. 2. Proceed as in the previous exercise, by adding n2 to both sides and simplifying. 3. The theorem is obvious for one summand. We then have that |x1 + x2 + · · · + xn| ≤ |x1 + x2 + · · · xn−1| + |xn| ≤ |x1| + |x2| + · · · |xn−1| + |xn|, as required, where the first inequality follows from the triangle inequality, and the second uses the induction hypothesis. 4. Define 0! = 1 and n! = n · (n − 1)! for n > 0. 5. Note that here your base case for induction is when n = 4. (You can easily check that this statement is false for n = 1, 2, and 3.) For the induction step, we have that 2n = 2 · 2n−1 < 2 · (n − 1)! < n · (n − 1)! = n!, as required, where the first inequality holds by the induction hypothesis, and the second because 2 < n. 6. In this exercise proceed as in Exercises 1 and 2 by adding the nth term n3 to the equation given by the induction hypothesis for n − 1. 7. We first show (by induction) this is true for a = 1, and then just multiply by a. As in Exercises 1, 2 and 6, merely add the nth term to the equation from the induction hypothesis. 8. The algebra here is simple if we apply the partial fraction decomposition 1 1 1 n(n + 1) = n − n + 1 . This makes it simple to apply the usual strategy of adding the nth term to both sides. 9. 4 (see Theorem 2.4). 10. A complete graph on 1 point has 0 edges. If n > 1, select a point and consider the subgraph on the remaining n − 1 points. By the induction hypothesis, this subgraph has (n − 1)(n − 2)/2 edges (lines). But the selected point has n − 1 edges connected to it, for a total of (n − 1)(n − 2)/2 + n − 1 = n(n − 1)/2 edges. 11. The base case is when n = 1 and when n = 2. For the induction step, assume n > 2. Then an = 2an−1 − an = 2 − 1 = 1, as required. K23541_SM_Cover.indd 2 11/18/14 7:13 PM n n+1 − − √ = √ . Σ n− 1 Σ n− 1 Σ n− 1 Σ n− 1 Σ n− 1 k 0 1 Σ 4 12. Note the base case consists of when n = 1 and n = 2. Assume n > 2. Then an = 3an−1 − 2an−2 = 3(3 + 2n−1) − 2(3 + 2n−2) = 3 + 6 · 2n−2 − 2 · 2n−2 = 3 + 2n, as required. 13. (a) Here, the base case is when n = 2. For the induction step, assume n > 2; we then have an+2an = (an+1 + an)an = an+1an + a2 . Use the induction hypothesis to replace the square term to get an+2an = an+1an + an+1an−1 − (−1)n = a2 + (−1)n+1, as required. (b) Here, the base case is when n = 1, 2. We then have an+1 = an + an−1 = (1 + √5)n (1 + √5)n 2n√5 + (1 + √5)n−1 (1 + √5)n−1 2n−1√5 = 2(1 + √5)n − 2(1 + √5)n + 4(1 + √5)n−1 − 4(1 − √5)n−1 2n+1 5 (6 + 2√5)(1 + √5)n−1 − (6 − 2√5)(1 − √5)n−1 2n+1 5 But t√he result follows when we check that (1 + √
5)2 = 6 + 2√
5 and (1 − √
5)2 = 6 − 2 5. 14. (a) Simplify the right hand side of the equation, by finding a common denominator. (b) If n = 1, then 1 = 1 and 1 = 1. Now if n > 1, the right hand side of the equation in part (a) is the sum of two integers, by the induction hypothesis. (c) In the induction step, (x + y)n = (x + y)(x + y)n−1 = (x + y) n−1 xn−1−kyk k n−1 = xn−kyk + k k=0 nΣ−1 n − 1 k=0 n−1 xn−1−kyk+1 k k=0 nΣ−2 n − 1 Now, we perform a change of variable on the right sum replacing k with k − 1 (thus the sum runs from 1 to n − 1): = xn + n−1 xn−kyk + n−1 xn−kyk + yn k k=1 k=1 k − 1 = xn + nΣ−1 n − 1 n − 1 xn−kyk + yn k k=1 nΣ−1 n k − 1 = k=0 n xn−kyk, n k k=1 k k=0 k k=1 = xn + xn−kyk + xn−1−kyk+1 + yn = xn + xn−kyk + yn + K23541_SM_Cover.indd 3 11/18/14 7:13 PM ∈ ∈ ∈ ∈ ∈ ∈ ⊂ \ | · · · · · · 0 n 5 this last step because n = n = 1. 15. The “induction” step is false when n = 2. 16. Let X N be non -empty with no least element and let Y = N X. Since X has no least element, 1 Y . Now, suppose k Y for all k < n. Thus k / X for all k < n. If n X, then n would be the least element in X, thus n / X and so n Y . Therefore Y satisfies criteria (1) and (2) of the Principle of Mathematical Induction and so Y = N. That is, X = ∅, a contradiction. 17. Hint: It’s probably easier to prove that the Strong Principle is equivalent to the Well - ordering Principle. This works because of Theorem 1.1 and Exercise 16. Chapter 2 — The Integers 1. (a) (13)(21) + (−8)(34) = 1 (b) (157)(772) + (−50)(2424) = 4 (c) (−53)(2007) + (524)(203) = 1 (d) (4)(3604) + (−3)(4770) = 106 2. (a) Note that gcd( a, b) divides both a and b. (b) gcd( a, b) must divide 3, so is either 1 or 3. But 3 divides both these integers. (c) gcd( a, b) is either 1, 2, or 4. But the integers are odd, and so the gcd is 1. (d) Note this does not essentially speed up the process in the last 3 cases. In part (a) gcd( a, b) is either 1 or 13. 3. There are two things to prove here: each linear combination of a and b is a multiple of gcd( a, b) and each multiple of gcd( a, b) can be written as a linear combination of a and b. The latter part follows from the GCD identity. For the former, note that a common divisor of a and b also divides ax + by. 4. This follows immediately from Exercise 3. 5. The base case n = 1 is trivial. For induction, assume p a 1a2 an = (a1a2 an−1)an, for n > 1, and then apply the prime property, and induction. 6. Note that gcd( a, b) divides a + b. 7. (a) Consider (n + 1)! + 2, (n + 1)! + 3, · · · , (n + 1)! + (n + 1). (a) 6! + 2. Of course, there might be a run of 5 earlier. 8. Use induction on n. Note that if d divides b and a + b, d divides a. 9. Use the GCD identity: Let g = gcd( b, c). Then g = bx+cy and this is the least positive linear combination of b and c. Now suppose h = gcd( ab, ac ) = abx′+acy′ = a(bx′+cy′). Now if bx′ + cy′ were not the least such positive linear combination then a smaller such would lead to a smaller linear combination of ab and ac to get h. 10. First, the given term clearly divides both a and b. Now suppose d is a common divisor of a and b. Now if p is a prime dividing d then it must be one of the primes listed in both a and b and its power is no larger than si. Thus d divides the gcd( a, b) given. K23541_SM_Cover.indd 4 11/18/14 7:13 PM ≤ k 6 11. 22 · 3 · 5 · 19, 2 · 5 · 32 · 7. In place of the si use the larger of ni and mi. 12. This follows easily using the formulations from Exercises 10 and 11. 13. By way of contradiction, assume lcm( a, b ) = x does not divide m. By the Division Theorem, x = dm + r, where 0 r < x. Argue that r is a common multiple of a and b. This forces r = 0. 14. Use contradiction assuming that √
2 = a/b where a and b are relatively prime. Square both sides and clear the denominator, and then consider whether each side is even or odd. Your contradiction will be that both a and b are even. 15. (a) That triangle DEP is isoscel es follo√ws from the observation that triangle ADP is isosceles. Now note that s = r + 2r. (b) Hint: Consider the square with three vertices E, P , and C, and use part (a). Why does this mean that the algorithm never halts? (Consider what happens if d and s are integer multiples of a common value.) 16. If n is the smallest number divisible by primes p1 . . . pk and p is a different prime, then p does not divide n. Prove this by contradiction. 17. (a) Note the first recursive call is gcd(772 , 108). (b) The first recursive call (from gcd(285 , 255, g, x, y)) will be gcd(255 , 30, g, x, y). The next will be gcd(30 , 15, g, x, y ). The next last one is gcd(15 , 0, g, x, y ). These calls then return with values for g, x, and y. 18. (a) Note ri+2 = ri+1 · q + ri and ri < r i+1 < r i+2. So, if ri+1 ≤ 1/2 ri+2 we’re done. Suppose ri+1 > 1/2 ri+2. Then ri+2 = ri+1 · q + (ri+2 − ri+1) and ri+2 − ri+1 < 1/2 ri+2. (b) So, in the worst case, the remainder is halved every 2 steps. Thus if it takes 2 n steps for the remainder to reach 1, max( a, b )/2n = 1 So, n ≈ log2(max( a, b )). Thus, it will take about 2 log2(max( a, b)) steps. 19. We know from Exercise 1.14 that p is an integer. But p = p! . k (p − k)!k! The denominator of this quotient is not divisible by the prime p, because it is a product of integers strictly less than p. However, the numerator is obviously divisible by p. Thus the quotient must also be divisible by p. Chapter 3 — Modular Arithmetic 1. [0]8 = {. . . , −16, −8, 0, 8, . . .}, [1]8 = {. . . , −16, −7, 1, 9, . . .}, [2]8 = {. . . , −14, −6, 2, 10, . . .}, [3]8 = {. . . , −13, −5, 3, 11, . . .}, [4]8 = {. . . , −12, −4, 4, 12, . . .}, [5]8 = {. . . , −11, −3, 5, 11, . . .}, [6]8 = {. . . , −10, −2, 6, 14, . . .}, [7]8 = {. . . , −9, −1, 7, 15, . . .}. [1] 1 = [1]8, [3]8−1 = [3]8, [5]−8 1 = [5]8, [7]−8 1 = [7]8. 2. [1], [2], [4], [7], [8], [11], [13], [14]; [3]X = [2].
5)2 = 6 + 2√
5 and (1 − √
5)2 = 6 − 2 5. 14. (a) Simplify the right hand side of the equation, by finding a common denominator. (b) If n = 1, then 1 = 1 and 1 = 1. Now if n > 1, the right hand side of the equation in part (a) is the sum of two integers, by the induction hypothesis. (c) In the induction step, (x + y)n = (x + y)(x + y)n−1 = (x + y) n−1 xn−1−kyk k n−1 = xn−kyk + k k=0 nΣ−1 n − 1 k=0 n−1 xn−1−kyk+1 k k=0 nΣ−2 n − 1 Now, we perform a change of variable on the right sum replacing k with k − 1 (thus the sum runs from 1 to n − 1): = xn + n−1 xn−kyk + n−1 xn−kyk + yn k k=1 k=1 k − 1 = xn + nΣ−1 n − 1 n − 1 xn−kyk + yn k k=1 nΣ−1 n k − 1 = k=0 n xn−kyk, n k k=1 k k=0 k k=1 = xn + xn−kyk + xn−1−kyk+1 + yn = xn + xn−kyk + yn + K23541_SM_Cover.indd 3 11/18/14 7:13 PM ∈ ∈ ∈ ∈ ∈ ∈ ⊂ \ | · · · · · · 0 n 5 this last step because n = n = 1. 15. The “induction” step is false when n = 2. 16. Let X N be non -empty with no least element and let Y = N X. Since X has no least element, 1 Y . Now, suppose k Y for all k < n. Thus k / X for all k < n. If n X, then n would be the least element in X, thus n / X and so n Y . Therefore Y satisfies criteria (1) and (2) of the Principle of Mathematical Induction and so Y = N. That is, X = ∅, a contradiction. 17. Hint: It’s probably easier to prove that the Strong Principle is equivalent to the Well - ordering Principle. This works because of Theorem 1.1 and Exercise 16. Chapter 2 — The Integers 1. (a) (13)(21) + (−8)(34) = 1 (b) (157)(772) + (−50)(2424) = 4 (c) (−53)(2007) + (524)(203) = 1 (d) (4)(3604) + (−3)(4770) = 106 2. (a) Note that gcd( a, b) divides both a and b. (b) gcd( a, b) must divide 3, so is either 1 or 3. But 3 divides both these integers. (c) gcd( a, b) is either 1, 2, or 4. But the integers are odd, and so the gcd is 1. (d) Note this does not essentially speed up the process in the last 3 cases. In part (a) gcd( a, b) is either 1 or 13. 3. There are two things to prove here: each linear combination of a and b is a multiple of gcd( a, b) and each multiple of gcd( a, b) can be written as a linear combination of a and b. The latter part follows from the GCD identity. For the former, note that a common divisor of a and b also divides ax + by. 4. This follows immediately from Exercise 3. 5. The base case n = 1 is trivial. For induction, assume p a 1a2 an = (a1a2 an−1)an, for n > 1, and then apply the prime property, and induction. 6. Note that gcd( a, b) divides a + b. 7. (a) Consider (n + 1)! + 2, (n + 1)! + 3, · · · , (n + 1)! + (n + 1). (a) 6! + 2. Of course, there might be a run of 5 earlier. 8. Use induction on n. Note that if d divides b and a + b, d divides a. 9. Use the GCD identity: Let g = gcd( b, c). Then g = bx+cy and this is the least positive linear combination of b and c. Now suppose h = gcd( ab, ac ) = abx′+acy′ = a(bx′+cy′). Now if bx′ + cy′ were not the least such positive linear combination then a smaller such would lead to a smaller linear combination of ab and ac to get h. 10. First, the given term clearly divides both a and b. Now suppose d is a common divisor of a and b. Now if p is a prime dividing d then it must be one of the primes listed in both a and b and its power is no larger than si. Thus d divides the gcd( a, b) given. K23541_SM_Cover.indd 4 11/18/14 7:13 PM ≤ k 6 11. 22 · 3 · 5 · 19, 2 · 5 · 32 · 7. In place of the si use the larger of ni and mi. 12. This follows easily using the formulations from Exercises 10 and 11. 13. By way of contradiction, assume lcm( a, b ) = x does not divide m. By the Division Theorem, x = dm + r, where 0 r < x. Argue that r is a common multiple of a and b. This forces r = 0. 14. Use contradiction assuming that √
2 = a/b where a and b are relatively prime. Square both sides and clear the denominator, and then consider whether each side is even or odd. Your contradiction will be that both a and b are even. 15. (a) That triangle DEP is isoscel es follo√ws from the observation that triangle ADP is isosceles. Now note that s = r + 2r. (b) Hint: Consider the square with three vertices E, P , and C, and use part (a). Why does this mean that the algorithm never halts? (Consider what happens if d and s are integer multiples of a common value.) 16. If n is the smallest number divisible by primes p1 . . . pk and p is a different prime, then p does not divide n. Prove this by contradiction. 17. (a) Note the first recursive call is gcd(772 , 108). (b) The first recursive call (from gcd(285 , 255, g, x, y)) will be gcd(255 , 30, g, x, y). The next will be gcd(30 , 15, g, x, y ). The next last one is gcd(15 , 0, g, x, y ). These calls then return with values for g, x, and y. 18. (a) Note ri+2 = ri+1 · q + ri and ri < r i+1 < r i+2. So, if ri+1 ≤ 1/2 ri+2 we’re done. Suppose ri+1 > 1/2 ri+2. Then ri+2 = ri+1 · q + (ri+2 − ri+1) and ri+2 − ri+1 < 1/2 ri+2. (b) So, in the worst case, the remainder is halved every 2 steps. Thus if it takes 2 n steps for the remainder to reach 1, max( a, b )/2n = 1 So, n ≈ log2(max( a, b )). Thus, it will take about 2 log2(max( a, b)) steps. 19. We know from Exercise 1.14 that p is an integer. But p = p! . k (p − k)!k! The denominator of this quotient is not divisible by the prime p, because it is a product of integers strictly less than p. However, the numerator is obviously divisible by p. Thus the quotient must also be divisible by p. Chapter 3 — Modular Arithmetic 1. [0]8 = {. . . , −16, −8, 0, 8, . . .}, [1]8 = {. . . , −16, −7, 1, 9, . . .}, [2]8 = {. . . , −14, −6, 2, 10, . . .}, [3]8 = {. . . , −13, −5, 3, 11, . . .}, [4]8 = {. . . , −12, −4, 4, 12, . . .}, [5]8 = {. . . , −11, −3, 5, 11, . . .}, [6]8 = {. . . , −10, −2, 6, 14, . . .}, [7]8 = {. . . , −9, −1, 7, 15, . . .}. [1] 1 = [1]8, [3]8−1 = [3]8, [5]−8 1 = [5]8, [7]−8 1 = [7]8. 2. [1], [2], [4], [7], [8], [11], [13], [14]; [3]X = [2].
