Abstract Algebra : An Introduction, 3rd Edition Solution Manual

© Cengage Learning. All rights reserved. No distribution allowed without express authorization. Chapter 2 Congruence in Z and Modular Arithmetic 2.1 Congruence and Congruence Classes − 1. (a) 25–1 = 24 = 16 ≡ 1 (mod 5). (b) 47 1 = 46 = 4096 ≡ 1 (mod 7). 11−1 10 (c) 3 = 3 = 59049 ≡ 1 (mod 11). 2. (a) Use Theorems 2.1 and 2.2: 6k + 5 ≡ 6.1 + 5 ≡ 11 ≡ 3 (mod 4). (b)2r + 3s ≡ 2.3 + 3.(–7) ≡ –15 ≡ 5 (mod 10). 3. (a) Computing the checksum gives 10 · 3 + 9 · 5 + 8 · 4 + 7 · 0 + 6 · 9 + 5 · 0 + 4 · 5 + 3 · 1 + 2 · 8 + 1 · 9 = 30 + 45 + 32 + 54 + 20 + 3 + 16 + 9 = 209. Since 209 = 11 · 19, we see that 209 ≡ 0 (mod 11), so that this could be a valid ISBN number. (b) Computing the checksum gives 10 · 0 + 9 · 0 + 8 · 3 + 7 · 1 + 6 · 1 + 5 · 0 + 4 · 5 + 3 · 5 + 2 · 9 + 1 · 5 = 24 + 7 + 6 + 20 + 15 + 18 + 5 = 95. Since 95 = 11 · 8 + 7, we see that 95 ≡ 7 (mod 11), so that this could not be a valid ISBN number. (c) Computing the checksum gives 10 · 0 + 9 · 3 + 8 · 8 + 7 · 5 + 6 · 4 + 5 · 9 + 4 · 5 + 3 · 9 + 2 · 6 + 1 · 10 = 27 + 64 + 35 + 24 + 45 + 20 + 27 + 12 + 10 = 264. Since 264 = 11 · 24, we see that 264 ≡ 0 (mod 11), so that this could be a valid ISBN number. © 2013 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed with a certain product or service or otherwise on a password-protected website for classroom use. Congruence in Z and Modular Arithmetic 12 4. (a) Computing the checksum gives 3 · 0 + 3 + 3 · 7 + 0 + 3 · 0 + 0 + 3 ˙ 3 + 5 + 3 · 6 + 6 + 3 · 9 + 1 = 90. Since 90 = 10 · 9, we have 90 ≡ 0 (mod 10), so that this was scanned correctly. (b) Computing the checksum gives 3 · 8 + 3 + 3 · 3 + 7 + 3 · 3 + 2 + 3 ˙ 0 + 0 + 3 · 0 + 6 + 3 · 2 + 5 = 71. (c) Computing the checksum gives 3 · 0 + 4 + 3 · 0 + 2 + 3 · 9 + 3 + 3 ˙ 6 + 7 + 3 · 3 + 0 + 3 · 3 + 4 = 83. Since 83 = 10 · 8 + 3, we have 83 ≡ 3 (mod 10), so that this was not scanned correctly. 5. Since 5 ≡ 1 (mod 4), it follows from Theorem 2.2 that 52 ≡ 12 (mod 4), so that (applying Theorem 1000 2.2 again) 53 ≡ 13 (mod 4). Continuing, ≡ 11000 ≡ 1 (mod 4). Since 51000 ≡ 1 1000 we get 5 (mod 4), Theorem 2.3 tells us that 5 = [1] in Z4 . 6. Given n ⎟ (a – b) so that a – b = nq for some integer q. Since k ⎟ n it follows that k ⎟ (a – b) and therefore a ≡ b (mod k). 7. By Corollary 2.5, a ≡ 0, 1, 2 or 3 (mod 4). Theorem 2.2 implies a2 ≡ 0, 1 (mod 4). Therefore a2 cannot be congruent to either 2 or 3 (mod 4). 8. By the division algorithm, any integer n is expressible as n = 4q + r where r ∈ {0, 1, 2, 3}, and n ≡ r (mod 4). If r is 0 or 2 then n is even. Therefore if n is odd then n ≡ 1 or 3 (mod 4). 9. (a) (n − a)2 ≡ n2 – 2na + a2 ≡ a2 (mod n) since n ≡ 0 (mod n). (b) (2n − a)2 ≡ 4n2 – 4na + a2 ≡ a2 (mod 4n) since 4n ≡ 0 (mod 4n). 10. Suppose the base ten digits of a are (cncn–1 . . . c1co). (Compare Exercise 1.2.32). Then a = cn10n + cn−110n−1 +. . . c110 + c0 ≡ c0 (mod 10), since 10k ≡ 0 (mod 10) for every k ≥ 1. 11. Since there are infinitely many primes (Exercise 1.3.25) there exists a prime p > ⎪a – b⎪. By hypothesis, p ⎪ (a – b) so the only possibility is a – b = 0 and a = b. 12. If p ≡ 0, 2 or 4 (mod 6), then p is divisible by 2. If p ≡ 0 or 3 (mod 6) then p is divisible by 3. Since p is a prime > 3 these cases cannot occur, so that p ≡ 1 or 5 (mod 6). By Theorem 2.3 this says that [p] = [1] or [5] in Z6. 13. Suppose r, r’ are the remainders for a and b, respectively. Theorem 2.3 and Corollary 2.5 imply: a ≡ b (mod n) if and only if [a] = [b] if and only if [r] = [r’]. Then r = r’ as in the proof of Corollary 2.5(2). © 2013 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed with a certain product or service or otherwise on a password-protected website for classroom use. © Cengage Learning. All rights reserved. No distribution allowed without express authorization. Since 71 = 10 · 7 + 1, we have 71 ≡ 1 (mod 10), so that this was not scanned correctly. 2.2 Modular Arithmetic 13 14. (a) Here is one example: a = b = 2 and n = 4. (b) The assertion is: if n ⎪ ab then either n ⎪ a or n ⎪b. This is true when n is prime by Theorem 1.8. 15. Since (a, n) = 1 there exist integers u, v such that au + nv = 1, by Theorem 1.3. Therefore au ≡ au + nv ≡ 1 (mod n), and we can choose b = u. © Cengage Learning. All rights reserved. No distribution allowed without express authorization. 16. Given that a ≡ 1 (mod n), we have a = nq + 1 for some integer q. Then (a, n) must divide a − nq = 1, so (a, n) = 1. One example to see that the converse is false is to use a = 2 and n = 3. Then (a, n) = 1 but [a] ≠ [1]. 17. Since 10 ≡ –1 (mod 11), Theorem 2.2 (repeated) shows that 10n ≡ (–l)n (mod 11). 18. By Exercise 23 we have 125698 ≡ 31 ≡ 4 (mod 9), 23797 ≡ 28 ≡ 1 (mod 9) and 2891235306 ≡ 39 ≡ 12 ≡ 3 (mod 9). Since 4⋅1 ≢ 3 (mod 9) the conclusion follows. 19. Proof: If [a] = [b] then a ≡ b (mod n) so that a = b + nk for some integer k. Then (a, n) = (b, n) using Lemma 1.7. 20. (a) One counterexample occurs when a = 0, b = 2 and n = 4. (b) Given a2 ≡ b2 (mod n), we have n ⎪ (a2 – b2) = (a + b)(a – b). Since n is prime, use Theorem 1.8 to conclude that either n⎪(a + b) or n ⎪ (a − b).Therefore, either a ≡ b (mod n) or a ≡ −b (mod n). 21. (a) Since 10 ≡ 1 (mod 9), Theorem 2.2 (repeated) shows that 10n ≡ 1 (mod 9). (b) (Compare Exercise 1.2.32). Express integer a in base ten notation: a = cn10n + . . . + c110+ c0 . Then a ≡ cn+ cn – t + . . . c1 + c0 (mod 9), since 10k ≡ 1 (mod 9). 22. (a) Here is one example: a = 2, b = 0, c = 2, n = 4. (b) We have n | ab – ac = a(b – c). Since (a, n) = l Theorem 1.5 implies that n ⎪(b – c) and therefore b ≡ c (mod n). 2.2 Modular Arithmetic 1. (a) Answered in the text. (b) + 0 1 2 3 0 0 1 2 3 1 1 2 3 0 2 2 3 0 1 3 3 0 1 2 – 0 1 2 3 0 0 0 0 0 1 0 1 2 3 2 0 2 0 2 3 0 3 2 1 © 2013 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed with a certain product or service or otherwise on a password-protected website for classroom use. Congruence in Z and Modular Arithmetic 14 (d) + 0 1 2 3 4 5 6 7 8 9 10 11 0 0 1 2 3 4 5 6 7 8 9 10 11 1 1 2 3 4 5 6 7 8 9 10 11 0 2 2 3 4 5 6 7 8 9 10 11 0 1 3 3 4 5 6 7 8 9 10 11 0 1 2 4 4 5 6 7 8 9 10 11 0 1 2 3 5 5 6 7 8 9 10 11 0 1 2 3 4 6 6 7 8 9 10 11 0 1 2 3 4 5 7 7 8 9 10 11 0 1 2 3 4 5 6 8 8 9 10 11 0 1 2 3 4 5 6 7 9 9 10 11 0 1 2 3 4 5 6 7 8 10 10 11 0 1 2 3 4 5 6 7 8 9 11 11 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 11 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 2 3 4 5 6 7 8 9 10 11 2 0 2 4 6 8 10 0 2 4 6 8 10 3 0 3 6 9 0 3 6 9 0 3 6 9 4 0 4 8 0 4 8 0 4 8 0 4 8 5 0 5 10 3 8 1 6 11 4 9 2 7 6 0 6 0 6 0 6 0 6 0 6 0 6 7 0 7 2 9 4 11 6 1 8 3 10 5 8 0 8 4 0 8 4 0 8 4 0 8 4 9 0 9 6 3 0 9 6 3 0 9 6 3 10 0 10 8 6 4 2 0 10 8 6 4 2 11 0 11 10 9 8 7 6 5 4 3 2 1 However, the notation must be changed to correspond to the new notation. See the tables in Example 2 to see what it must look like. 2. To solve x2 ⊕ x = [0] in Z4 , substitute each of [0], [1], [2], and [3] in the equation to see if it is a solution: x x2 ⊕ x Is x2 ⊕ x = [0]? [0] [0] ⊗ [0] ⊕ [0] = [0] + [0] = [0] Yes; solution. [1] [1] ⊗ [1] ⊕ [1] = [1] + [1] = [2] No. [2] [2] ⊗ [2] ⊕ [2] = [0] + [2] = [2] No. [3] [3] ⊗ [3] ⊕ [3] = [1] ⊕ [3] = [0] Yes; solution. 3. x = 1, 3, 5 or 7 in ℤ0. However, the notation should be changed to use, for example, [3] instead of 3. © 2013 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed with a certain product or service or otherwise on a password-protected website for classroom use. © Cengage Learning. All rights reserved. No distribution allowed without express authorization. (c) Answered in the text. 2.2 Modular Arithmetic 15 4. x = 1, 2, 3 or 4 in ℤ 5. However, the notation should be changed to use, for example, [3] instead of 3. 5. x = 1, 2, 4, 5 in ℤ 6. However, the notation should be changed to use, for example, [3] instead of 3. 6. To solve x2 ⊕ [8] ⊗ x = [0] in Z9 , substitute each of [0], [1], [2], . . . , [8] in the equation to see if it is a solution: © Cengage Learning. All rights reserved. No distribution allowed without express authorization. x x2 ⊕ [8] ⊗ x Is x2 ⊕ [8] ⊗ x = [0]? [0] [0] ⊗ [0] ⊕ [8] ⊗ [0] = [0] + [0] = [0] Yes; solution. [1] [1] ⊗ [1] ⊕ [8] ⊗ [1] = [1] + [8] = [0] Yes; solution. [2] [2] ⊗ [2] ⊕ [8] ⊗ [2] = [4] + [7] = [2] No. [3] [3] ⊗ [3] ⊕ [8] ⊗ [3] = [0] ⊕ [6] = [6] No. [4] [4] ⊗ [4] ⊕ [8] ⊗ [4] = [7] ⊕ [5] = [3] No. [5] [5] ⊗ [5] ⊕ [8] ⊗ [5] = [7] ⊕ [4] = [2] No. [6] [6] ⊗ [6] ⊕ [8] ⊗ [6] = [0] ⊕ [3] = [3] No. [7] [7] ⊗ [7] ⊕ [8] ⊗ [7] = [4] ⊕ [2] = [6] No. [8] [8] ⊗ [8] ⊕ [8] ⊗ [8] = [1] ⊕ [1] = [2] No. The solutions are x = [0] and x = [1]. 7. To solve x3 ⊕ x2 ⊕ x ⊕ [1] = [0] in Z8 , substitute each of [0], [1], [2], . . . , [7] in the equation to see if it is a solution: x x3 ⊕ x2 ⊕ x ⊕ [1] Is x3 ⊕ x2 ⊕ x ⊕ [1] = [0]? [0] [1] No. [1] [4] No. [2] [7] No. [3] [0] No. [4] [5] No. [5] [4] No. [6] [3] No. [7] [0] Yes; solution. The only solution is x = [7]. 8. To solve x3 + x2 = [2] in Z10 , substitute each of [0], [1], . . . , [9] in the equation to see if it is a © 2013 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed with a certain product or service or otherwise on a password-protected website for classroom use. Congruence in Z and Modular Arithmetic 16 x x 3 ⊕ x2 Is x3 ⊕ x2 = [2]? [0] [0] No. [1] [2] Yes; solution. [2] [2] Yes; solution.. [3] [6] No. [4] [0] No. [5] [0] No. [6] [2] Yes; solution. [7] [2] Yes; solution. [8] [6] No. [9] [0] No. The solutions are x = [1], [2], [6], and [7]. 9. (a) a = 3 or 5. (b) a = 2 or 3. (c) No such element exists in ℤ 6. However, the notation should be changed to use, for example, [3] instead of 3. 10. Part 3: [a] ⊕ [b] = [a + b] = [b + a] = [b] ⊕ [a] since a + b = b + a in ℤ. Part 7: [a]  ([b]  [c]) = [a]  [be] = [a(bc)] = [(ab)c] = [ab]  [c] = ([a]  [b])  [c]. Part 8: [a]  ([b] ⊕ [c]) = [a]  [b + c] = [a(b + c)] = [ab + ac] = [ab] ⊕ [ac] = ([a]  [b]) ⊕ ([a  [c]). Part 9: [a]  [b] = [ab] = [ba] = [b]  [a]. 11. Every value of x satisfies these equations. 12. See Exercise 2.1.14. 13. See Exercise 2.1.22. 14. (a) x = 0 or 4 in ℤ 5. (b) x = 0, 2, 3 or 5 in ℤ 6. However, the notation should be changed to use, for example, [3] instead of 3. © 2013 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed with a certain product or service or otherwise on a password-protected website for classroom use. © Cengage Learning. All rights reserved. No distribution allowed without express authorization. solution: 2.3 The Structure of Zp (p Prime) and Zn 15. (a) (a + b)5 = a5 + b5 in ℤ 5. 17 (b) (a + b)3 = a3 + b3 in ℤ 3. (c) (a + b)2 = a2 + b2 in ℤ 2. (d) One is led to conjecture that (a + b)7 = a7 + b7 in ℤ 7 . To investigate the general result for any prime exponent, use the Binomial Theorem and Exercise 1.4.13. © Cengage Learning. All rights reserved. No distribution allowed without express authorization. However, the notation should be changed to use, for example, [a] instead of a . 16. (a) a = 1, 2, 3 or 4 in ℤ 5. (b) a = 1 or 3 in ℤ 4. (c) a = 1 or 2 in ℤ 3 (d) a = l or 5 in ℤ 6. However, the notation should be changed to use, for example, [3] instead of 3. 2.3 The Structure of Zp (p Prime) and Zn 1. (a) 1, 2, 3, 4, 5, 6 (b) 1, 3, 5, 7 (c) 1, 2, 4, 5, 7, 8 (d) 1, 3, 7, 9 2. (a) Since 7 is prime, part (3) of Theorem 2.8 says that there are no zero divisors in Z7 . (b) The zero divisors are 2, 4, and 6, since 2 · 4 = 0 and 6 · 4 = 0. Further computations will show that the other elements of Z8 are not zero divisors. (c) The zero divisors are 3 and 6, since 3 · 6 = 0. Further computations will show that the other elements of Z9 are not zero divisors. (d) The zero divisors are 2, 4, 5, 6, and 8, since 2 · 5 = 4 · 5 = 6 · 5 = 8 · 5 = 0. Further computations will show that the other elements of Z10 are not zero divisors. 3. In Zn , it appears that every nonzero element is either a unit or a zero divisor. 4. (a) 1 solution in ℤ 7 (b) 2 solutions in ℤ 8 (c) 0 solutions in ℤ 9 (d) 2 solutions in ℤ |0. 5. We first show that ab 6= 0. If ab = 0, then since a is a unit, then a−1 ab = 0, so that b = 0. But b is a zero divisor, so that b 6= 0 and thus ab 6= 0. Now, since b is a zero divisor, choose c 6= 0 such that bc = 0; then (ab)c = a(bc) = 0 shows that ab is also a zero divisor. 6. Since n is composite, write n = ab where 1 < a, b < n. Then in Zn , [a] 6= 0 and [b] 6= 0, since both a and b are less than n, but [a][b] = [ab] = [n] = 0, so that a and b are zero divisors. 7. If ab = 0 in ℤ p then ab ≡ 0 (mod p) so that p ⎪ ab. By Theorem 1.8 we conclude that p ⎪ a or p ⎪ b. Then a ≡ 0 (mod p) or b ≡ 0 (mod p). Equivalently, a = 0 or b = 0 in ℤ p . 8. (a) For instance choose a even and b odd. (b) Yes. 9. (a) Suppose a is a unit. Choose b such that ab = 0. Then since a is a unit, we have a−1 ab = a−1 0 = 0, so that b = 0. Thus a is not a zero divisor, since any such b must be zero. (b) This statement is the contrapositive of part (a), so is also true. © 2013 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed with a certain product or service or otherwise on a password-protected website for classroom use. Congruence in Z and Modular Arithmetic 18 11. Since a is a unit, the equation ax = b has the solution a−1 b, since aa−1 b = b. Now, suppose that ax = b and also ay = b. Then a(x − y) = 0. Since a is not a zero divisor, and a 6= 0 since it is a unit, it follows that x − y = 0 so that x = y. Hence the solution is unique. 12. If x = [r] is a solution then [ar] = [b] so that ar ≡ b (mod n) and ar – b = kn for some integer k. Then d ⎪ a and d ⎪ n implies d ⎪ (ar – kn) = b. 13. Since d divides each of a, b and n there are integers a1, n1, b1. with a = da1, b = db1. and n = dn1. By Theorem 1.3 there are integers u, v with au + nv = d so that au ≡ d (mod n). Therefore a(ub1) ≡ b1d = b (mod n) so that x = [ub1] is one solution. Since an1 = a1dn1 = a1n ≡ 0 (mod n) we see that x = [ub1 + n1t] is a solution for every integer t. 14. (a) If [ub1 + sn1] and [ub1 + tn1] are equal in ℤn for some 0 ≤ s < t < d, then n ⎪ (tn1 – sn1) = (t – s)n1 so that d ⎪ (t – s) contrary to 0 < (t – s) < d. (b) If x = [r] is a solution then [ar] = [b] = [a ⋅ ub1] so that n ⎪ a(r – ub1) so that a(r – ub1) = nw for some integer w. Cancel d to obtain a1(r – ub1) = n1w. Since (a1, n1) = 1, (Why?) Theorem 1.5 implies n1⎪(r – ub1) so that r = ub1 + tn1 for some t. Then x = [r] = [ub1 + tn1]. Divide t by d to get t = dq + k where 0 ≤ k < d. Then x = [ub1 + (dq + k)n1] = [ub1 + kn1] because [dn1] = [n] = [0]. 15. (a) 15x = 9 in Z18 if and only if 15x ≡ 9 (mod 18) if and only if 5x ≡ 3 (mod 6) if and only if x ≡ 3 (mod 6) if and only if x ≡ 3, 9, 15 (mod 18) if and only if x = [3], [9], [15] in Z18. (b) x = 3, 16, 29, 42 or 55 in Z65. 16. By Exercise 10, every nonzero element of Zn is a unit or a zero divisor, but not both. So the statement we are trying to prove is equivalent to the following statement: If a 6= 0 and b are elements of Zn and ax = b has no solutions in Zn , prove that a is not a unit. The contrapositive of this statement, which is equivalent to the statement itself, is: If a 6= 0 and b are elements of Zn and a is a unit, then ax = b has at least one solution in Zn . But Exercise 11 proves this statement. 17. Suppose that a and b are units. Then (ab)(b−1 a−1 ) = a(bb−1 )a−1 = aa−1 = 1, so that ab is a unit. 18. See the Hint when 0 < 1. Otherwise, if 0 6< 1, then since 0 = 1, we must have 1 < 0 since we have fully ordered Zn . Adding 1 to both sides repeatedly, using rule (ii), gives n−1 < n−2 < · · · < 1 < 0, so that, by rule (i), n − 1 < 0. Now add 1 to both sides to get 0 < 1, which is a contradiction. © 2013 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed with a certain product or service or otherwise on a password-protected website for classroom use. © Cengage Learning. All rights reserved. No distribution allowed without express authorization. 10. No element can be both a unit and a zero divisor, by Exercise 9. Choose x 6= 0 ∈ Zn , and consider the set of products {x · 1, x · 2, . . . , x · (n − 1)}. This set has n − 1 elements. If x is not a zero divisor, then 0 is not one of those elements. So there are two possibilities: either no element is duplicated in that list, or there is a duplicate. If there is no duplicate, then since there are n − 1 elements and n − 1 possible values, one of the elements must be 1; that is, for some a ∈ Zn , we have x · a = 1. Thus x is a unit. If there is a duplicate, say x · a = x · b, then x · (a − b) = 0, so that x is a zero divisor, which contradicts our original assumption. This shows that if x is not a zero divisor, then it is a unit.