Skip to content
Textbook Guides

Abstract Algebra : An Introduction, 3rd Edition Solution Manual

Simplify your textbook learning with Abstract Algebra : An Introduction, 3rd Edition Solution Manual, providing step-by-step solutions to every chapter.

Preview 16 of 206 pages

See the first 16 pages exactly as they appear in the document.

  1. Page 1
    Read page 1 as text

    C O N T E N T S Chapter 1 ℤ ...................................................................................... 1 Chapter 2 ℤ ........................................................... 11 Chapter 3 ..................................................................................................................... 19 Chapter 4 F ................................................................................................ 45 Chapter 5 F ....................................... 63 Chapter 6 .................................................................................... 69 Chapter 7 ................................................................................................................... 83 Chapter 8 ........................................................... 113 Chapter 9 ..................................................................................... 133 Chapter 10 ......................................................................... 147 Chapter 11 ................................................................................................. 159 Chapter 12 .................................................................................................... 171 Chapter 13 .................................................................................. 179 Chapter 14 ..................................................................... 181 Chapter 15 ................................................................................... 185 Chapter 16 .................................................................................. 189

  2. Page 2
  3. Page 3
  4. Page 4
    Read page 4 as text

    Chapter 1 Arithmetic in Revisited 1.1 The Division Algorithm 1. (a) q = 4, r = 1. (b) q = 0, r = 0. (c) q = − 5, r = 3. 2. (a) q = − 9, r = 3. (b) q = 15, r = 17. (c) q = 117, r = 11. 3. (a) q = 6, r = 19. (b) q = − 9, r = 54. (c) q = 62720, r = 92. 4. (a) q = 15021, r = 132. (b) q = − 14940, r = 335. (c) q = 39763, r = 3997. 5. Suppose a = bq + r , with 0 ≤ r < b . Multiplying this equation through by c gives ac = ( bc ) q + rc . Further, since 0 ≤ r < b , it follows that 0 ≤ rc < bc . Thus this equation expresses ac as a multiple of bc plus a remainder between 0 and bc − 1. Since by Theorem 1.1 this representation is unique, it must be that q is the quotient and rc the remainder on dividing ac by bc . 6. When q is divided by c , the quotient is k , so that q = ck . Thus a = bq + r = b ( ck ) + r = ( bc ) k + r . Further, since 0 ≤ r < b , it follows (since c ≥ 1) than 0 ≤ r < bc . Thus a = ( bc ) k + r is the unique representation with 0 ≤ r < bc , so that the quotient is indeed k . 7. 8. 9. 10. Answered in the text. Any integer n can be divided by 4 with remainder r equal to 0, 1, 2 or 3. Then either n = 4 k , 4 k + 1, 4 k + 2 or 4 k + 3, where k is the quotient. If n = 4 k or 4 k + 2 then n is even. Therefore if n is odd then n = 4 k + 1 or 4 k + 3. We know that every integer a is of the form 3 q , 3 q + 1 or 3 q + 2 for some q . In the last case a = (3 q + 2) 3 = 27 q 3 + 54 q 2 + 36 q + 8 = 9 k + 8 where k = 3 q 3 + 6 q 2 + 4 q . Other cases are similar. Suppose a = nq + r where 0 ≤ r < n and c = nq ' + r ' where 0 < r ' < n . If r = r ' then a – c = n( q – q ' ) and k = q – q ' is an integer. Conversely, given a – c = nk we can substitute to find: ( r – r ') = n ( k – q + q ' ). Suppose r ≥ r (the other case is similar). The given inequalities imply that 0 ≤ ( r – r ' ) < n and it follows that 0 ≤ ( k – q + q ' ) < 10000 k – q + q ' = 0. Therefore r – r ' = 0, so that r = r ' as claimed. 3 1 and we conclude that ' Z

  5. Page 5
    Read page 5 as text

    1.2 Divisibility 1. (a) 8. (b) 6. (c) 1. (d) 11. (e) 9. (f) 17. (g) 592. (h) 6. 2. 3. 4. 5. Since a | b , we have b = ak for some integer k , and a 6 = 0. Since b | a , we have a = bl for some integer l , and b 6 = 0. Thus a = bl = ( ak ) l = a ( kl ). Since a 6 = 0, divide through by a to get 1 = kl . But this means that k = ± 1 and l = ± 1, so that a = ± b . 6. 7. Clearly ( a, 0) is at most | a | since no integer larger than | a | divides a . But also | a | | a , and | a | | 0 since any nonzero integer divides 0. Hence | a | is the gcd of a and 0. 8. 9. No, ab need not divide c . For one example, note that 4 | 12 and 6 | 12, but 4 · 6 = 24 does not divide 12. 10. 11. 12. (a) False. ( ab, a ) is always at least a since a | ab and a | a . (b) False. For example, (2 , 3) = 1 and (2 , 9) = 1, but (3 , 9) = 3. (c) False. For example, let a = 2, b = 3, and c = 9. Then (2 , 3) = 1 = (2 , 9), but (2 · 3 , 9) = 3. 11. Given integers a and c with c ≠ 0. Apply Theorem 1.1 with b = |c| to get a = |c| . q + r where 0 ≤ r < |c|. Let q = q 0 if c > 0 and q = – q 0 if c < 0. Then a = cq + r as claimed. The uniqueness is proved as in Theorem 1.1. If b | a then a = bx for some integer x . Then a = (– b )(– x ) so that (– b ) | a . The converse follows similarly. Answered in the text. (a) Given b = ax and c = ay for some integers x , y , we find b + c = ax + ay = a ( x + y ). Since x + y is an integer, conclude that a | ( b + c ). (b) Given x and y as above we find br + ct = ( ax ) r + ( ay ) t = a ( xr + yt ) using the associative and distributive laws. Since xr + yt is an integer we conclude that a | ( br + ct ). Given b = ax and d = cy for some integers x , y , we have bd = ( ax )( cy ) = ( ac )( xy ). Then ac | bd because xy is an integer. If d = ( n , n + 1) then d | n and d | ( n + 1). Since ( n + 1) – n = 1 we conclude that d | 1. (Apply Exercise 4( b ).) This implies d = 1, since d > 0. Since a | a and a | 0 we have a | ( a , 0). If ( a , 0) = 1 then a | 1 forcing a = ±1. (a) 1 or 2 (b) 1, 2, 3 or 6. Generally if d = ( n , n + c ) then d | n and d | ( n + c ). Since c is a linear combination of n and n+c, conclude that d | c . 0 Arithmetic in Z Revisited 2

  6. Page 6
    Read page 6 as text

    14. 15. (a) This is a calculation. (b) At the first step, for example, by Exercise 13 we have ( a, b ) = (524 , 148) = (148 , 80) = ( b, r ). The same applies at each of the remaining steps. So at the final step, we have (8 , 4) = (4 , 0); putting this string of equalities together gives (524 , 148) = (148 , 80) = (80 , 68) = (68 , 12) = (12 , 8) = (8 , 4) = (4 , 0) . But by Example 4, (4 , 0) = 4, so that (524 , 148) = 4. (c) 1003 = 56 · 17 + 51, 56 = 51 · 1 + 5, 51 = 5 · 10 + 1, 5 = 1 · 5 + 0. Thus (1003 , 56) = (1 , 0) = 1. (d) 322 = 148 · 2 + 26, 148 = 26 · 5 + 18, 26 = 18 · 1 + 8, 18 = 8 · 2 + 2, 8 = 2 · 4 + 0, so that (322 , 148) = (2 , 0) = 2. (e) 5858 = 1436 · 4 + 114, 1436 = 114 · 12 + 68, 114 = 68 · 1 + 46, 68 = 46 · 1 + 22, 46 = 22 · 2 + 2, 22 = 2 · 11 + 0, so that (5858 , 1436) = (2 , 0) = 2. (f) 68 = 148 − (524 − 148 · 3) = − 524 + 148 · 4. (g) 12 = 80 − 68 · 1 = (524 − 148 · 3) − ( − 524 + 148 · 4) · 1 = 524 · 2 − 148 · 7. (h) 8 = 68 − 12 · 5 = ( − 524 + 148 · 4) − (524 · 2 − 148 · 7) · 5 = − 524 · 11 + 148 · 39. (i) 4 = 12 − 8 = (524 · 2 − 148 · 7) − ( − 524 · 11 + 148 · 39) = 524 · 13 − 148 · 46. (j) Working the computation backwards gives 1 = 1003 · 11 − 56 · 197. 16. 17. Since b | c , we know that c = bt for some integer t . Thus a | c means that a | bt . But then Theorem 1.4 tells us, since ( a, b ) = 1, that a | t . Multiplying both sides by b gives ab | bt = c . 18. 19. 1.2 Divisibility 3 13. (a) Suppose c | a and c | b . Write a = ck and b = cl . Then a = bq + r can be rewritten ck = ( cl ) q + r , so that r = ck − clq = c ( k − lq ). Thus c | r as well, so that c is a common divisor of b and r . (b) Suppose c | b and c | r . Write b = ck and r = cl , and substitute into a = bq + r to get a = ckq + cl = c ( kq + l ). Thus c | a , so that c is a common divisor of a and b . (c) Since ( a, b ) is a common divisor of a and b , it is also a common divisor of b and r , by part (a). If ( a, b ) is not the greatest common divisor ( b, r ) of b and r , then ( a, b ) > ( b, r ). Now, consider ( b, r ). By part (b), this is also a common divisor of ( a, b ), but it is less than ( a, b ). This is a contradiction. Thus ( a, b ) = ( b, r ). By Theorem 1.3, the smallest positive integer in the set S of all linear combinations of a and b is exactly ( a , b ). ( a ) (6, 15) = 3 ( b ) (12, 17)=1. Let a = da 1 and b = db 1 . Then a 1 and b 1 are integers and we are to prove: ( a 1 , b 1 ) = l. By Theorem 1.3 there exist integers u , v such that au + bv = d . Substituting and cancelling we find that a 1 u + b 1 v = l. Therefore any common divisor of a 1 and b 1 must also divide this linear combination, so it divides 1. Hence ( a 1 , b 1 ) = 1. Let d = ( a , b ) so there exist integers x, y with ax + by = d . Note that cd | ( ca , cb ) since cd divides ca and cb . Also cd = cax + cby so that ( ca , cb ) | cd . Since these quantities are positive we get cd = ( ca , cd ). Let d = ( a , b ). Since b + c = aw for some integer w , we know c is a linear combination of a and b so that d | . But then d | ( b ) = 1 forcing d = 1. Similarly ( ) = 1. c c , c , a

  7. Page 7
    Read page 7 as text

    23. 24. 25. 26. 27. 28. Suppose the integer consists of the digits a n a n − 1 . . . a 1 a 0 . Then the number is equal to n ∑ k =0 a k 10 k = n ∑ k =0 a k (10 k − 1) + n ∑ k =0 a k . Now, the first term consists of terms with factors of the form 10 k − 1, all of which are of the form 999 . . . 99, which are divisible by 3, so that the first term is always divisible by 3. Thus ∑ n k =0 a k 10 k is divisible by 3 if and only if the second term ∑ n k =0 a k is divisible by 3. But this is the sum of the digits. 29. This is almost identical to Exercise 28. Suppose the integer consists of the digits a n a n − 1 . . . a 1 a 0 . Then the number is equal to n ∑ k =0 a k 10 k = n ∑ k =0 a k (10 k − 1) + n ∑ k =0 a k . Now, the first term consists of terms with factors of the form 10 k − 1, all of which are of the form 999 . . . 99, which are divisible by 9, so that the first term is always divisible by 9. Thus ∑ n k =0 a k 10 k is divisible by 9 if and only if the second term ∑ n k =0 a k is divisible by 9. But this is the sum of the digits. Arithmetic in Z Revisited 4 20. 21. 22. Let d = ( a , b ) and e = ( a , b + at ). Since b + at is a linear combination of a and b , d | ( b + at ) so that d | e . Similarly since b = a (– t ) + ( b + at ) is a linear combination of a and b + at we know e | b so that e | d . Therefore d = e . Answered in the text. Let d = ( a , b , c ). Claim: ( a , d ) = l. [Proof: ( a , d ) divides d so it also divides c . Then ( a , d ) | ( a , c ) = 1 so that ( a , d )= 1.] Similarly ( b , d )= 1. But d | ab and ( a , d ) = 1 so that Theorem 1.5 implies that d | b. Therefore d = ( b . d ) = 1. Define the powers b n recursively as follows: b 1 = b and for every n ≥ 1, b n + 1 = b . b n . By hypothesis ( a , b 1 ) = 1. Given k ≥ 1, assume that ( a , b k ) = 1. Then ( a , b k + 1 ) = ( a , b . b k ) = 1 by Exercise 24. This proves that ( a , b n ) = 1 for every n ≥ 1. Let d = ( a , b ). If ax + by = c for some integers x, y then c is a linear combination of a and b so that d | c . Conversely suppose c is given with d | c, say c = dw for an integer w. By Theorem 1.3 there exist integers u , v with d = au + bv . Then c = dw = auw + bvw and we use x = uw and y = vw to solve the equation. (a) Given au + bv = 1 suppose d = ( a , b ). Then d | a and d | b so that d divides the linear combination au + bv = 1. Therefore d = 1. (b) There are many examples. For instance if a = b = d = u = v a , b ) = (1, 1)= 1 while d = au + bv = 1 + 1 = 2. Let d = ( a , b ) and express a = da 1 and b = db 1 for integers a 1 , b 1 . By Exercise 16, ( a 1 , b 1 ) = 1. Since a | c we have c = au = da 1 u for some integer u . Similarly c = bv = d b 1 v for some integer v . Then a 1 u = c / d = b 1 V and Theorem 1.5 implies that a 1 | v so that v = a 1 w for some integer w . Then c = da 1 b 1 w so that cd = d 2 a 1 b 1 w = abw and ab | cd . Answered in the text. = 1 then (

  8. Page 8
    Read page 8 as text

    31. (a) [6 , 10] = 30; [4 , 5 , 6 , 10] = 60; [20 , 42] = 420, and [2 , 3 , 14 , 36 , 42] = 252. (b) Suppose a i | t for i = 1 , 2 , . . . , k , and let m = [ a 1 , a 2 , . . . , a k ]. Then we can write t = mq + r with 0 ≤ r < m . For each i , a i | t by assumption, and a i | m since m is a common multiple of the a i . Thus a i | ( t − mq ) = r . Since a i | r for each i , we see that r is a common multiple of the a i . But m is the smallest positive integer that is a common multiple of the a i ; since 0 ≤ r < m , the only possibility is that r = 0 so that t = mq . Thus any common multiple of the a i is a multiple of the least common multiple. 32. First suppose that t = [ a, b ]. Then by definition of the least common multiple, t is a multiple of both a and b , so that t | a and t | b . If a | c and b | c , then c is also a common multiple of a and b , so by Exercise 31, it is a multiple of t so that t | c . Conversely, suppose that t satisfies the conditions (i) and (ii). Then since a | t and b | t , we see that t is a common multiple of a and b . Choose any other common multiple c , so that a | c and b | c . Then by condition (ii), we have t | c , so that t ≤ c . It follows that t is the least common multiple of a and b . 33. Let d = ( a, b ), and write a = da 1 and b = db 1 . Write m = ab d = da 1 db 1 d = da 1 b 1 . Since a and b are both positive, so is m , and since m = da 1 b 1 = ( da 1 ) b 1 = ab 1 and m = da 1 b 1 = ( db 1 ) a 1 = ba 1 , we see that m is a common multiple of a and b . Suppose now that k is a positive integer with a | k and b | k . Then k = au = bv , so that k = da 1 u = db 1 v . Thus k d = a 1 u = b 1 v . By Exercise 16, ( a 1 , b 1 ) = 1, so that a 1 | v , say v = a 1 w . Then k = db 1 v = db 1 a 1 w = mw , so that m | k . Thus m ≤ k . It follows that m is the least common multiple. But by construction, m = ab ( a,b ) = ab d . 34. (a) Let d = ( a, b ). Since d | a and d | b , it follows that d | ( a + b ) and d | ( a − b ), so that d is a common divisor of a + b and a − b . Hence it is a divisor of the greatest common divisor, so that d = ( a, b ) | ( a + b, a − b ). (b) We already know that ( a, b ) | ( a + b, a − b ). Now suppose that d = ( a + b, a − b ). Then a + b = dt and a − b = du , so that 2 a = d ( t + u ). Since a is even and b is odd, d must be odd. Since d | 2 a , it follows that d | a . Similarly, 2 b = d ( t − u ), so by the same argument, d | b . Thus d is a common divisor of a and b , so that d | ( a, b ). Thus ( a, b ) = ( a + b, a − b ). (c) Suppose that d = ( a + b, a − b ). Then a + b = dt and a − b = du , so that 2 a = d ( t + u ). Since a and b are both odd, a + b and a − b are both even, so that d is even. Thus a = d 2 ( t + u ), so that d 2 | a . Similarly, d 2 | b , so that d 2 = ( a + b,a − b ) 2 | ( a, b ) | ( a + b, a − b ). Thus ( a, b ) = ( a + b,a − b ) 2 or ( a, b ) = ( a + b, a − b ). But since ( a, b ) is odd and ( a + b, a − b ) is even, we must have ( a + b,a − b ) 2 = ( a, b ), or 2( a, b ) = ( a + b, a − b ). 5 30. Let S = { a 1 x 1 + a 2 x 2 + … + a n x n : x 1 x 2 , ..., x are integers}. As in the proof of Theorem 1.3, S does contain some positive elements (for if a j ≠ 0 then a j 2 ∈ S is positive). By the Well Ordering Axiom this set S contains a smallest positive element, which we call t . Suppose t = a 1 u 1 + a 2 u 2 + … + a n u n for some integers u j . Claim. t = d . The first step is to show that t | a . By the division algorithm there exist integers q and r such that a 1 = tq + r with 0 ≤ r < t . Then r = a 1 – tq = a 1 (1 – u 1 q ) + a 2 (– u 2 q ) + … + a n (– u n q ) is an element of S . Since r < t (the smallest positive element of S ), we know r is not positive. Since r ≥ 0 the only possibility is r = 0. Therefore a 1 = tq and t | a 1 . Similarly we have t | a j for each j, and t is a common divisor of a 1 , a 2 , … , a n . Then t ≤ d by definition. On the other hand d divides each a j so d divides every integer linear combination of a 1 , a 2 , ... , a n . In particular, d | t . Since t > 0 this implies that d ≤ t and therefore d = t . 1.2 Divisibility 1

  9. Page 9
    Read page 9 as text

    Arithmetic in Z Revisited 5. 6. The possible remainders on dividing a number by 10 are 0 , 1 , 2 , . . . , 9. If the remainder on dividing p by 10 is 0 , 2 , 4 , 6, or 8, then p is even; since p > 2, p is divisible by 2 in addition to 1 and itself and cannot be prime. If the remainder is 5, then since p > 5, p is divisible by 5 in addition to 1 and itself and cannot be prime. That leaves as possible remainders only 1 , 3 , 7, and 9. 7. Since p | ( a + bc ) and p | a , we have a = pk and a + bc = pl , so that pk + bc = pl and thus bc = p ( l − k ). Thus p | bc . By Theorem 1.5, either p | b or p | c (or both). 8. (a) As polynomials, x n − 1 = ( x − 1)( x n − 1 + x n − 2 + · · · + x + 1) . (b) Since 2 2 n · 3 n − 1 = (2 2 · 3) n − 1 = 12 n − 1, by part (a), 12 n − 1 is divisible by 12 − 1 = 11. 9. 10. 6 2. (a) Since 2 5 − 1 = 31, and √ 31 < 6, we need only check divisibility by the primes 2, 3, and 5. Since none of those divides 31, it is prime. (b) Since 2 7 − 1 = 127, and √ 127 < 12, we need only check divisibility by the primes 2, 3, 5, 7, and 11. Since none of those divides 127, it is prime. (c) 2 11 − 1 = 2047 = 23 · 89. 3. They are all prime. 4. The pairs are { 3 , 5 } , { 5 , 7 } , { 11 , 13 } , { 17 , 19 } , { 29 , 31 } , { 41 , 43 } , { 59 , 61 } , { 71 , 73 } , { 101 , 103 } , { 107 , 109 } , { 137 , 139 } , { 149 , 151 } , { 179 , 181 } , { 191 , 193 } , { 197 , 199 } . 1.3 Primes and Unique Factorization 1. (a) 2 4 · 3 2 · 5 · 7. (b) − 5 · 7 · 67. (c) 2 · 5 · 4567. (d) 2 3 · 3 · 5 · 7 · 11 · 13 · 17. (a) Answered in the text. These divisors can be listed as 2 j . 3 k for 0 ≤ j ≤ s and 0 ≤ k ≤ t . (b) The number of divisors equals ( r + l)( s + l)( t + 1) If p is a prime and p = rs then by the definition r, s must lie in {1, –1, p , – p r = ±1 or r = ± p and s = p/r = ±1, Conversely if p is not a prime then it has a divisor r not in {1, –1, p , – p p = rs for some integer s. If s equals ±1 or ± p then r = p / s would equal ± p or +1, contrary to assumption. This r , s provides an example where the given statement fails. Assume first that p > 0. If p is a prime then ( a , p ) is a positive divisor of p , so that ( a , p ) = 1 or p . If ( a , p ) = p then p | a . Conversely if p is not a prime it has a divisor d other than ±1 and ± p . We may change signs to assume d > 0. Then ( p , d ) = d ≠ l. Also p | d since otherwise p | d and d = p implies d = p . Then a = d provides an example where the required statement fails. Finally if p < 0 apply the argument above to – p . . }. Then either }. Then

  10. Page 10
    Read page 10 as text

    1.3 Primes and Unique Factorization 15. 16. 17. 18. 19. If r i ≤ s i for every i , then b = p s 1 1 p s 2 2 . . . p s k k = p r 1 1 p s 1 − r 1 1 p r 2 2 p s 2 − r 2 2 . . . p r k k p s k − r k k = ( p r 1 1 p r 2 2 . . . p r k k ) · ( p s 1 − r 1 1 p s 2 − r 2 2 . . . p s 2 − r k k ) = a · ( p s 1 − r 1 1 p s 2 − r 2 2 . . . p s 2 − r k k ) . Since each s i − r i ≥ 0, the second factor above is an integer, so that a | b . Now suppose a | b , and consider p r i i . Since this is composed of factors only of p i , it must divide p s i i , since p i - p j for i 6 = j . Thus p r i i | p s i i . Clearly this holds if r i ≤ s i , and also clearly it does not hold if r i > s i , since then p r i i > p s i i . 7 13. By Theorem 1.8, the Fundamental Theorem of Arithmetic, every integer except 0 and ± 1 can be written as a product of primes, and the representation is unique up to order and the signs of the primes. Since in our case n > 1 is positive and we wish to use positive primes, the representation is unique up to order. So write n = q 1 q 2 . . . q s where each q i > 0 is prime. Let p 1 , p 2 , . . . , p r be the distinct primes in the list. Collect together all the occurrences of each p i , giving r i copies of p i , i.e. p r i i . 14. 11. Since p | a − b and p | c − d , also p | ( a − b ) + ( c − d ) = ( a + c ) − ( b + d ). Thus p is a divisor of ( a + c ) − ( b + d ); the fact that p is prime means that it is a prime divisor. 12. Suppose d | p so that p = dt for some integer t . The hypothesis then implies that p | d or p | t . If p | d then ( a pplying Exercise 1.2.5) d = ± p . Similarly if p | t then, since we know that t | p , we get t = + p , and therefore d = ±1. Apply Corollary 1.9 in the case a 1 = a 2 = … = a n to see that if p | a n then p | a . Then a = pu for some integer u , so that a n = p n u n and p n | a n . Generally, p | a and p | b if and only if p | ( a , b ), as in Corollary 1.4. Then the Exercise is equivalent to: ( a , b ) = 1 if and only if there is no prime p such that p | ( a , b ). This follows using Theorem 1.10. First suppose u , v are integers with ( u , v ) = 1. Claim. ( u 2 , v 2 ) = 1. For suppose p is a prime such that p | u 2 and p | v 2 . Then p | u and p | v (using Theorem 1.8), contrary to the hypothesis ( u , v ) = 1. Then no such prime exists and the Claim follows by Exercise 8. Given ( a , b ) = p write a = pa 1 and b = pb 1 . Then ( a 1 , b 1 ) = 1 by Exercise 1.2.16. Then ( a 2 , b 2 ) = ( p 2 a 1 2 , p 2 b 1 2 ) = p 2 ( a 1 2 , b 1 2 ), using Exercise 1.2.18. By the Claim we conclude that ( a 2 , b 2 ) = p 2 . The choices p = 2, a = b = 0, c = d = 1 provide a counterexample to (a) and (b). (c) Since p | ( a 2 + b 2 ) – a . a = b 2 , conclude that p | b by Theorem 1.8. Since n > 1 Theorem 1.10 implies that n equals a product of primes. We can pull out minus signs to see that n = p 1 p 2 … p r where each p j is a positive prime. Re-ordering these primes if necessary, to assume p 1 ≤ p 2 ≤ … ≤ p r . For the uniqueness, suppose there is another factorization n = q 1 q 2 … q s for some positive primes q j with q 1 ≤ q 2 … ≤ q s . By theorem 1.11 we know that r = s and the p j ’s are just a re-arrangement of the q j s. Then p 1 is the smallest of the p j ’s, so it also equals the smallest of the q j ’s and therefore p 1 = q 1 . We can argue similarly that p 2 = q 2 , …, p r = q r . (This last step should really be done by a formal proof invoking the Well Ordering Axiom.)

  11. Page 11
    Read page 11 as text

    Arithmetic in Z Revisited 25. The binomial coefficient ( p k ) is ( p k ) = p ! k !( p − k )! = p · ( p − 1) · · · ( p − k + 1) k ( k − 1) · · · 1 . Now, the numerator is clearly divisible by p . The denominator, however, consists of a product of integers all of which are less than p . Since p is prime, none of those integers (except 1) divide p , so the product cannot have a factor of p (to make this more precise, you may wish to write the denominator as a product of primes and note that p cannot appear in the list). 26. 27. 24. This is almost identical to the previous exercise. If n > 0 is an integer, suppose a = p r 1 1 p r 2 2 . . . p r k k and b = p s 1 1 p s 2 2 . . . p s k k where the p i are distinct positive primes and r i ≥ 0, s i ≥ 0. Then a n = p nr 1 1 p nr 2 2 . . . p nr k k and b 2 = p ns 1 1 p ns 2 2 . . . p ns k k . Then using Exercise 19 (twice), we have a | b if and only if r i ≤ s i for each i if and only if nr i ≤ ns i for each i if and only if a n | b n . 8 22. 23. Suppose a = p r 1 1 p r 2 2 . . . p r k k and b = p s 1 1 p s 2 2 . . . p s k k where the p i are distinct positive primes and r i ≥ 0, s i ≥ 0. Then a 2 = p 2 r 1 1 p 2 r 2 2 . . . p 2 r k k and b 2 = p 2 s 1 1 p 2 s 2 2 . . . p 2 s k k . Then using Exercise 19 (twice), we have a | b if and only if r i ≤ s i for each i if and only if 2 r i ≤ 2 s i for each i if and only if a 2 | b 2 . 20. 21. (a) The positive divisors of a are the numbers d = p 1 m 1 p 2 m 2 … p k mk where the exponents m j satisfy 0 ≤ m j ≤ r j for each j = 1, 2,,.., k . This follows from unique factorization. If d also divides b we have 0 ≤ m j ≤ s j for each i = 1, 2,... k . Since n j = min{ r j , s j } we see that the positive common divisors of a and b are exactly those numbers d = p 1 m 1 p 2 m 2 … p k mk where 0 ≤ m j ≤ n j for each j = 1, 2,..., k . Then ( a , b ) is the largest among these common divisors, so it equals p 1 n 1 p 2 n 2 … p k nk . (b) For [ a , b ] a similar argument can be given, or we can apply Exercise 1.2.31, noting that max{ r , s } = r + s – min{ r , s } for any positive numbers r , s . Answered in the text. If every r i is even it is easy to see that n is a perfect square. Conversely suppose n is a square. First consider the special case n = p r is a power of a prime. If p r = m 2 is a square, consider the prime factorization of m. By the uniqueness (Theorem 1.11), p is the only prime that can occur, so m = p s for some s, and p r = m 2 = p 2 s . Then r = 2 s ' is even. Now for the general case, suppose n = m 2 is a perfect square. If some r i is odd, express n = p i ri . k where k is the product of the other primes involved in n . Then p i ri and k are relatively prime and Exercise 13 implies that p i ri is a perfect square. By the special case, r i . is even. Claim: Each A k = ( n + 1)! + k is composite, for k = 2, 3,. .. , n + 1. Proof. Since k ≤ n + have k | ( n + 1)! and therefore k | A k . Then A k is composite since I < k < A k . 12 k + 3 is a multiple of 3. Similarly if p = 6 k + 5 then p 2 +2 = 36 k 2 + 60 k + 27 is a multiple of 3. So in each case, p 2 + 2 is composite. By the division algorithm p = 6 k + r where 0 ≤ r < 6. Since p > 3 is prime it is not divisible by 2 or 3, and we must have r = 1 or 5. If p = 6 k + 1 then p 2 = 36 k 2 + 12 k + 1 and p 2 + 2 = 36 k 2 + 1 we

  12. Page 12
    Read page 12 as text

    33. Suppose n is composite, and write n = rs where 1 < r, s < n . Then, as you can see by multiplying it out, 2 n − 1 = (2 r − 1) ( 2 s ( r − 1) + 2 s ( r − 2) + 2 s ( r − 3) + · · · + 2 s + 1 ) . Since r > 1, it follows that 2 r > 1. Since s > 1, we see that 2 s + 1 > 1, so that the second factor must also be greater than 1. So 2 n − 1 has been written as the product of two integers greater than one, so it cannot be prime. 34. 35. 36. 9 1.3 Primes and Unique Factorization 31. 32. 30. 29. This assertion follows immediately from the Fundamental Theorem 1.11. (b) If 2 is rational it can be expressed as a fraction a b for some positive integers a, b. Clearing denominators and squaring leads to: a 2 = 2 b 2 , and part (a) applies. The argument in Exercise 20 applies. More generally see Exercise 27 below. Suppose all the primes can be put in a finite list p 1 , p 2 , … , p k and consider N = p 1 p 2 … p k + 1. None of these p j can divide N (since 1 can be expressed as a linear combination of p j and N ). But N > 1 so N must have some prime factor p . (Theorem 1.10). This p is a prime number not equal to any of the primes in our list, contrary to hypothesis. Proof: Since n > 2 we know that n ! – 1 > 1 so it has some prime factor p . If p ≤ n then p | n !, contrary to the fact that p | n n < p < n !. We sketch the proof ( b ). Suppose a > 0 (What if a < 0?), r n = a and r = u / v where u , v are integers and v > 0. Then u n = av u . If p is a prime let k be the exponent of p occurring in a (that is: p k | a and 1 | k p a + ). The exponents of p occurring in u n and in v n must be multiples of n , so unique factorization implies k is a multiple of n . Putting all the primes together we conclude that a = b n for some integer b . If p is a prime > 3 then 2 | p and 3 | p , so by Exercise 1.2.34 we know 24 | p 2 – 1. Similarly 24 | ( q 2 – 1) so that p 2 – q 2 = ( p 2 – 1) – ( q 2 – 1) is a multiple of 24. 28. The sums in question are: 1 + 2 + 4 + … + 2 n . When n = 7 the sum is 255 = 3 . 5 . 17 and when n = 8 the sum is 511 = 7 . 73. Therefore the assertion is false. The interested reader can verify that this sum equals 2 n +1 – 1. These numbers are related to the “Mersenne primes”. (a) If a 2 = 2 b 2 for positive integers a, b, compare the prime factorizations on both sides. The power of 2 occurring in the factorization of a 2 must be even (since it is a square). The power of 2 occurring in 2 b 2 must be odd. By the uniqueness of factorizations (The Fundamental Theorem) these powers of 2 must be equal, a contradiction. !. Therefore

  13. Page 13
  14. Page 14
    Read page 14 as text

    Chapter 2 Congruence in Z and Modular Arithmetic 2.1 Congruence and Congruence Classes 1. 2. 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. (a) 2 5–1 = 2 4 = 16 ≡ 1 (mod 5). (b) 4 7 − 1 = 4 6 = 4096 ≡ 1 (mod 7). (c) 3 11 − 1 = 3 10 = 59049 1 (mod 11). (a) Use Theorems 2.1 and 2.2: 6 k + 5 ≡ 6.1 + 5 ≡ 11 ≡ 3 (mod 4). (b)2 r + 3 s ≡ 2.3 + 3.(–7) ≡ –15 ≡ 5 (mod 10). ≡

  15. Page 15
    Read page 15 as text

    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 . Since 71 = 10 · 7 + 1, we have 71 ≡ 1 (mod 10), so that this was not scanned correctly. (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 5 2 ≡ 1 2 (mod 4), so that (applying Theorem 2.2 again) 5 3 ≡ 1 3 (mod 4). Continuing, we get 5 1000 ≡ 1 1000 ≡ 1 (mod 4). Since 5 1000 ≡ 1 (mod 4), Theorem 2.3 tells us that [ 5 1000 ] = [1] in Z 4 . 6. 7. 8. 9. 10. 11. 12. 13. Congruence in Z and Modular Arithmetic 12 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 ). By Corollary 2.5, a ≡ 0, 1, 2 or 3 (mod 4). Theorem 2.2 implies a 2 ≡ 0, 1 (mod 4). Therefore a 2 cannot be congruent to either 2 or 3 (mod 4). By the division algorithm, any integer n is expressible as n = 4 q + 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). (a) ( n − a ) 2 ≡ n 2 – 2 na + a 2 ≡ a 2 (mod n ) since n ≡ 0 (mod n ). (b) (2 n − a ) 2 ≡ 4 n 2 – 4 na + a 2 ≡ a 2 (mod 4 n ) since 4 n ≡ 0 (mod 4 n ). Suppose the base ten digits of a are ( c n c n –1 . . . c 1 c o ). (Compare Exercise 1.2.32). Then a = c n 10 n + c n − 10 n − 1 +. . . c 1 10 + c 0 ≡ c 0 (mod 10), since 10 k ≡ 0 (mod 10) for every k ≥ 1. 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 . 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 6 . 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). Z 1

  16. Page 16
    Read page 16 as text

    14. 15. 16. 17. 18. 19. 20. 21. 22. 2.2 Modular Arithmetic 1. 13 (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. 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 . 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]. Since 10 ≡ –1 (mod 11), Theorem 2.2 (repeated) shows that 10 n ≡ (–l) n (mod 11). 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. 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. (a) One counterexample occurs when a = 0, b = 2 and n = 4. (b) Given a 2 ≡ b 2 (mod n ), we have n ⎪ ( a 2 – b 2 ) = ( 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 ). (a) Since 10 ≡ 1 (mod 9), Theorem 2.2 (repeated) shows that 10 n ≡ 1 (mod 9). (b) (Compare Exercise 1.2.32). Express integer a in base ten notation: a = c n 10 n c 1 10+ c 0 . Then a ≡ c n + c n - t + . . . c 1 + c 0 (mod 9), since 10 k ≡ 1 (mod 9). (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 ). (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 + . . . + – 2.2 Modular Arithmetic

190 more pages in the full document

Unlock it once and it stays in your library, ready to chat with or turn into flashcards.

Unlock the full document

More Mathematics study materials

See all

Study this document with CramX

Once it is in your library, every tool can work from it.