Abstract Algebra : An Introduction, 3rd Edition Solution Manual

Preview (16 of 206 Pages)

100%

Abstract Algebra : An Introduction, 3rd Edition Solution Manual - Page 1 preview image

Loading page ...

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

Abstract Algebra : An Introduction, 3rd Edition Solution Manual - Page 2 preview image

Loading page ...

Abstract Algebra : An Introduction, 3rd Edition Solution Manual - Page 3 preview image

Loading page ...

Abstract Algebra : An Introduction, 3rd Edition Solution Manual - Page 4 preview image

Loading page ...

Chapter 1Arithmetic inRevisited1.1The Division Algorithm1.(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. Supposea=bq+r, with 0≤r < b. Multiplying this equation through bycgivesac= (bc)q+rc.Further, since 0≤r < b, it follows that 0≤rc < bc. Thus this equation expressesacas a multipleofbcplus a remainder between 0 andbc−1. Since by Theorem 1.1 this representation is unique,it must be thatqis the quotient andrcthe remainder on dividingacbybc.6. Whenqis divided byc, the quotient isk, so thatq=ck. Thusa=bq+r=b(ck) +r= (bc)k+r.Further, since 0≤r < b, it follows (sincec≥1) than 0≤r < bc. Thusa= (bc)k+ris the uniquerepresentation with 0≤r < bc, so that the quotient is indeedk.7.8.9.10.Answered in the text.Any integerncan be divided by 4 with remainderrequal to 0, 1, 2 or 3. Then eithern= 4k,4k+ 1, 4k+ 2 or 4k+ 3, wherekis the quotient. Ifn= 4kor 4k+ 2 thennis even. Therefore ifnis odd thenn= 4k+ 1 or 4k+ 3.We know that every integerais of the form 3q, 3q+ 1 or 3q+ 2 for someq. In the last casea= (3q+ 2)3= 27q3+ 54q2+ 36q+ 8 = 9k+ 8 wherek= 3q3+ 6q2+ 4q. Other cases are similar.Supposea=nq+rwhere 0≤r<nandc=nq'+r'where 0 <r'<n. Ifr=r'thena–c=n(q–q') andk=q–q'is an integer. Conversely, givena–c=nkwe can substitute to find:(r–r')=n(k–q+q'). Supposer≥r(the other case is similar). The given inequalities implythat 0≤(r–r') <nand it follows that 0≤(k–q+q') <10000k–q+q'= 0.Thereforer–r'= 0, so thatr=r'as claimed.31 and we conclude that'Z

Abstract Algebra : An Introduction, 3rd Edition Solution Manual - Page 5 preview image

Loading page ...

1.2Divisibility1.(a) 8.(b) 6.(c) 1.(d) 11.(e) 9.(f) 17.(g) 592.(h) 6.2.3.4.5.Sincea|b, we haveb=akfor some integerk, anda6= 0.Sinceb|a, we havea=blfor someintegerl, andb6= 0. Thusa=bl= (ak)l=a(kl). Sincea6= 0, divide through byato get 1 =kl.But this means thatk=±1 andl=±1, so thata=±b.6.7.Clearly (a,0) is at most|a|since no integer larger than|a|dividesa. But also|a| |a, and|a| |0since any nonzero integer divides 0. Hence|a|is the gcd ofaand 0.8.9.No,abneed not dividec.For one example, note that 4|12 and 6|12, but 4·6 = 24 does notdivide 12.10.11.12.(a) False. (ab, a) is always at leastasincea|abanda|a.(b) False. For example, (2,3) = 1 and (2,9) = 1, but (3,9) = 3.(c) False. For example, leta= 2,b= 3, andc= 9. Then (2,3) = 1 = (2,9), but (2·3,9) = 3.11.Given integersaandcwithc≠0. Apply Theorem 1.1 withb= |c| to geta= |c| .q+rwhere 0≤r< |c|. Letq=q0ifc> 0 andq= –q0ifc< 0. Thena=cq+ras claimed. The uniqueness isproved as in Theorem 1.1.Ifb|athena=bxfor some integerx. Thena= (–b)(–x) so that (–b) |a. The converse followssimilarly.Answered in the text.(a)Givenb=axandc=ayfor some integersx,y, we findb+c=ax+ay=a(x+y).Sincex+yis an integer, conclude thata| (b+c).(b)Givenxandyas above we findbr+ct= (ax)r+ (ay)t=a(xr+yt) using the associativeand distributive laws. Sincexr+ytis an integer we conclude thata| (br+ct).Givenb=axandd=cyfor some integersx,y, we havebd= (ax)(cy) = (ac)(xy). Thenac|bdbecausexyis an integer.Ifd= (n,n+ 1) thend|nandd| (n+ 1). Since (n+ 1) –n= 1 we conclude thatd| 1. (ApplyExercise 4(b).) This impliesd= 1, sinced> 0.Sincea|aanda| 0 we havea| (a, 0). If (a, 0) = 1 thena| 1 forcinga= ±1.(a)1 or 2(b) 1, 2, 3 or 6. Generally ifd= (n,n+c) thend|nandd| (n+c).Sincecisalinear combination ofnand n+c, conclude thatd|c.0Arithmetic inZRevisited2

Abstract Algebra : An Introduction, 3rd Edition Solution Manual - Page 6 preview image

Loading page ...

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.Sinceb|c, we know thatc=btfor some integert. Thusa|cmeans thata|bt. But then Theorem1.4 tells us, since (a, b) = 1, thata|t. Multiplying both sides bybgivesab|bt=c.18.19.1.2 Divisibility313.(a) Supposec|aandc|b.Writea=ckandb=cl.Thena=bq+rcan be rewrittenck= (cl)q+r, so thatr=ck−clq=c(k−lq).Thusc|ras well, so thatcis a commondivisor ofbandr.(b) Supposec|bandc|r.Writeb=ckandr=cl, and substitute intoa=bq+rto geta=ckq+cl=c(kq+l). Thusc|a, so thatcis a common divisor ofaandb.(c) Since (a, b) is a common divisor ofaandb, it is also a common divisor ofbandr, by part (a).If (a, b) is not the greatest common divisor (b, r) ofbandr, 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 acontradiction. Thus (a, b) = (b, r).By Theorem 1.3, the smallest positive integer in the setSof all linear combinations ofaandbisexactly (a,b).(a) (6, 15) = 3(b) (12, 17)=1.Leta=da1andb=db1. Thena1andb1are integers and we are to prove: (a1,b1) = l. ByTheorem 1.3 there exist integersu,vsuch thatau+bv=d. Substituting and cancelling we findthata1u+b1v= l. Therefore any common divisor ofa1andb1must also divide this linearcombination, so it divides 1. Hence (a1,b1) = 1.Letd= (a,b) so there exist integersx,ywithax+by=d. Note thatcd| (ca,cb) sincecddividescaandcb. Alsocd=cax+cbyso that (ca,cb) |cd. Since these quantities are positive wegetcd= (ca,cd).Letd= (a,b). Sinceb+c=awfor some integerw, we knowcis a linear combination ofaandbso thatd| . But thend| (b) = 1 forcingd= 1. Similarly () = 1.cc,c,a

Abstract Algebra : An Introduction, 3rd Edition Solution Manual - Page 7 preview image

Loading page ...

23.24.25.26.27.28. Suppose the integer consists of the digitsanan−1. . . a1a0. Then the number is equal ton∑k=0ak10k=n∑k=0ak(10k−1) +n∑k=0ak.Now, the first term consists of terms with factors of the form 10k−1, all of which are of the form999. . .99, which are divisible by 3, so that the first term is always divisible by 3. Thus∑nk=0ak10kis divisible by 3 if and only if the second term∑nk=0akis divisible by 3. But this is the sum of thedigits.29. This is almost identical to Exercise 28. Suppose the integer consists of the digitsanan−1. . . a1a0.Then the number is equal ton∑k=0ak10k=n∑k=0ak(10k−1) +n∑k=0ak.Now, the first term consists of terms with factors of the form 10k−1, all of which are of the form999. . .99, which are divisible by 9, so that the first term is always divisible by 9. Thus∑nk=0ak10kis divisible by 9 if and only if the second term∑nk=0akis divisible by 9. But this is the sum of thedigits.Arithmetic inZRevisited420.21.22.Letd= (a,b) ande= (a,b+at). Sinceb+atis a linear combination ofaandb,d| (b+at) sothatd|e. Similarly sinceb=a(–t) + (b+at) is a linear combination ofaandb+atwe knowe|bso thate|d. Therefored=e.Answered in the text.Letd= (a,b,c). Claim: (a,d) = l. [Proof: (a,d) dividesdso it also dividesc. Then (a,d) | (a,c)= 1 so that (a,d)= 1.] Similarly (b,d)= 1. Butd|aband (a,d) = 1 so that Theorem 1.5 impliesthatd| b. Therefored= (b.d) = 1.Define the powersbnrecursively as follows:b1=band for everyn≥1,bn+ 1=b.bn. Byhypothesis (a,b1) = 1. Givenk≥1, assume that (a,bk) = 1. Then (a,bk+ 1) = (a,b.bk) = 1 byExercise 24. This proves that (a,bn) = 1 for everyn≥1.Letd= (a,b). Ifax+by=cfor some integersx,ythencisalinear combination ofaandbsothatd|c. Conversely supposecis given withd| c, sayc=dwfor an integerw.By Theorem 1.3there exist integersu,vwithd=au+bv. Thenc=dw=auw+bvwand we usex=uwandy=vwto solve the equation.(a) Givenau+bv= 1 supposed= (a,b). Thend|aandd|bso thatddivides the linearcombinationau+bv= 1. Therefored= 1.(b) There are many examples. For instance ifa=b=d=u=va,b) = (1, 1)= 1whiled=au+bv= 1 + 1 = 2.Letd= (a,b) and expressa=da1andb=db1for integersa1,b1. By Exercise 16, (a1,b1) = 1.Sincea|cwe havec=au=da1ufor some integeru. Similarlyc=bv= db1vfor some integerv.Thena1u=c/d=b1Vand Theorem 1.5 implies thata1|vso thatv=a1wfor some integerw.Thenc=da1b1wso thatcd=d2a1b1w=abwandab|cd.Answered in the text.= 1 then (

Abstract Algebra : An Introduction, 3rd Edition Solution Manual - Page 8 preview image

Loading page ...

31. (a) [6,10] = 30; [4,5,6,10] = 60; [20,42] = 420, and [2,3,14,36,42] = 252.(b) Supposeai|tfori= 1,2, . . . , k, and letm= [a1, a2, . . . , ak]. Then we can writet=mq+rwith 0≤r < m. For eachi,ai|tby assumption, andai|msincemis a common multipleof theai. Thusai|(t−mq) =r. Sinceai|rfor eachi, we see thatris a common multipleof theai.Butmis the smallest positive integer that is a common multiple of theai; since0≤r < m, the only possibility is thatr= 0 so thatt=mq. Thus any common multiple oftheaiis a multiple of the least common multiple.32. First suppose thatt= [a, b].Then by definition of the least common multiple,tis a multiple ofbothaandb, so thatt|aandt|b. Ifa|candb|c, thencis also a common multiple ofaandb,so by Exercise 31, it is a multiple oftso thatt|c.Conversely, suppose thattsatisfies the conditions (i) and (ii). Then sincea|tandb|t, we see thattis a common multiple ofaandb. Choose any other common multiplec, so thata|candb|c.Then by condition (ii), we havet|c, so thatt≤c. It follows thattis the least common multipleofaandb.33. Letd= (a, b), and writea=da1andb=db1. Writem=abd=da1db1d=da1b1. Sinceaandbareboth positive, so ism, and sincem=da1b1= (da1)b1=ab1andm=da1b1= (db1)a1=ba1, wesee thatmis a common multiple ofaandb. Suppose now thatkis a positive integer witha|kandb|k.Thenk=au=bv, so thatk=da1u=db1v.Thuskd=a1u=b1v.By Exercise 16,(a1, b1) = 1, so thata1|v, sayv=a1w.Thenk=db1v=db1a1w=mw, so thatm|k.Thusm≤k. It follows thatmis the least common multiple. But by construction,m=ab(a,b)=abd.34.(a) Letd= (a, b). Sinced|aandd|b, it follows thatd|(a+b) andd|(a−b), so thatdis acommon divisor ofa+banda−b. Hence it is a divisor of the greatest common divisor, sothatd= (a, b)|(a+b, a−b).(b) We already know that (a, b)|(a+b, a−b). Now suppose thatd= (a+b, a−b). Thena+b=dtanda−b=du, so that 2a=d(t+u).Sinceais even andbis odd,dmust be odd. Sinced|2a, it follows thatd|a. Similarly, 2b=d(t−u), so by the same argument,d|b. Thusdisa common divisor ofaandb, so thatd|(a, b). Thus (a, b) = (a+b, a−b).(c) Suppose thatd= (a+b, a−b). Thena+b=dtanda−b=du, so that 2a=d(t+u). Sinceaandbare both odd,a+banda−bare both even, so thatdis even. Thusa=d2(t+u), sothatd2|a. Similarly,d2|b, so thatd2=(a+b,a−b)2|(a, b)|(a+b, a−b). Thus (a, b) =(a+b,a−b)2or (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).530.LetS= {a1x1+a2x2+ … +anxn:x1x2, ...,xare integers}. As in the proof of Theorem 1.3,Sdoes contain some positive elements (for ifaj≠0 thenaj2∈Sis positive). By the Well OrderingAxiom this setScontains a smallest positive element, which we callt. Supposet=a1u1+a2u2+… +anunfor some integersuj.Claim.t=d. The first step is to show thatt|a. By the division algorithm there exist integersqandrsuch thata1=tq+rwith 0≤r<t. Thenr=a1–tq=a1(1 –u1q) +a2(–u2q) + … +an(–unq) is an element ofS. Sincer<t(the smallest positive element ofS), we knowris notpositive. Sincer≥0 the only possibility isr= 0. Thereforea1=tqandt|a1. Similarly we havet|ajfor eachj,andtisacommon divisor ofa1,a2,…,an. Thent≤dby definition.On the other handddivides eachajsoddivides every integer linear combination ofa1,a2,...,an.In particular,d|t. Sincet> 0 this implies thatd≤tand therefored=t.1.2 Divisibility1

Abstract Algebra : An Introduction, 3rd Edition Solution Manual - Page 9 preview image

Loading page ...

Arithmetic inZRevisited5.6. The possible remainders on dividing a number by 10 are 0,1,2, . . . ,9. If the remainder on dividingpby 10 is 0,2,4,6, or 8, thenpis even; sincep >2,pis divisible by 2 in addition to 1 and itselfand cannot be prime. If the remainder is 5, then sincep >5,pis divisible by 5 in addition to 1and itself and cannot be prime. That leaves as possible remainders only 1,3,7, and 9.7. Sincep|(a+bc) andp|a, we havea=pkanda+bc=pl, so thatpk+bc=pland thusbc=p(l−k). Thusp|bc. By Theorem 1.5, eitherp|borp|c(or both).8.(a) As polynomials,xn−1 = (x−1)(xn−1+xn−2+· · ·+x+ 1).(b) Since 22n·3n−1 = (22·3)n−1 = 12n−1, by part (a), 12n−1 is divisible by 12−1 = 11.9.10.62.(a) Since 25−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 27−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) 211−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.3Primes and Unique Factorization1.(a) 24·32·5·7.(b)−5·7·67.(c) 2·5·4567.(d) 23·3·5·7·11·13·17.(a)Answered in the text. These divisors can be listed as 2j.3kfor 0≤j≤sand 0≤k≤t.(b)The number of divisors equals (r+ l)(s+ l)(t+ 1)Ifpisaprime andp=rsthen by the definition r,smust lie in {1, –1,p, –pr= ±1orr= ±pands=p/r= ±1, Conversely ifpis not a prime then it has a divisorrnot in {1, –1,p, –pp=rsfor some integers.Ifsequals ±1 or ±pthenr=p/swould equal ±por +1,contrary to assumption. Thisr,sprovides an example where the given statement fails.Assume first thatp> 0. Ifpis a prime then (a,p) is a positive divisor ofp, so that (a,p) = 1 orp. If (a,p) =pthenp|a. Conversely ifpis not a prime it has a divisordother than ±1 and ±p.We may change signs to assumed> 0. Then (p,d) =d≠l. Alsop|dsince otherwisep|dandd=pimpliesd=p. Thena=dprovides an example where the required statement fails. Finallyifp< 0 apply the argument above to –p..}. Then either}. Then

Abstract Algebra : An Introduction, 3rd Edition Solution Manual - Page 10 preview image

Loading page ...

1.3 Primes and Unique Factorization15.16.17.18.19. Ifri≤sifor everyi, thenb=ps11ps22. . . pskk=pr11ps1−r11pr22ps2−r22. . . prkkpsk−rkk= (pr11pr22. . . prkk)·(ps1−r11ps2−r22. . . ps2−rkk)=a·(ps1−r11ps2−r22. . . ps2−rkk).Since eachsi−ri≥0, the second factor above is an integer, so thata|b.Now supposea|b, and considerprii. Since this is composed of factors only ofpi, it must dividepsii,sincepi-pjfori6=j. Thusprii|psii. Clearly this holds ifri≤si, and also clearly it does not holdifri> si, since thenprii> psii.713. By Theorem 1.8, the Fundamental Theorem of Arithmetic, every integer except 0 and±1 can bewritten as a product of primes, and the representation is unique up to order and the signs of theprimes. Since in our casen >1 is positive and we wish to use positive primes, the representationis unique up to order. So writen=q1q2. . . qswhere eachqi>0 is prime. Letp1, p2, . . . , prbe thedistinct primes in the list. Collect together all the occurrences of eachpi, givingricopies ofpi,i.e.prii.14.11. Sincep|a−bandp|c−d, alsop|(a−b) + (c−d) = (a+c)−(b+d). Thuspis a divisor of(a+c)−(b+d); the fact thatpis prime means that it is a prime divisor.12.Supposed|pso thatp=dtfor some integert. The hypothesis then implies thatp|dorp|t. Ifp|dthen (applying Exercise 1.2.5)d= ±p. Similarly ifp|tthen, since we know thatt|p, wegett= +p, and therefored= ±1.Apply Corollary 1.9 in the casea1=a2= … =anto see that ifp|anthenp|a. Thena=puforsome integeru, so thatan=pnunandpn|an.Generally,p|aandp|bif and only ifp| (a,b), as in Corollary 1.4. Then the Exercise isequivalent to: (a,b) = 1 if and only if there is no primepsuch thatp| (a,b). This follows usingTheorem 1.10.First supposeu,vare integers with (u,v) = 1. Claim. (u2,v2) = 1. For supposepisaprimesuch thatp|u2andp|v2. Thenp|uandp|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) =pwritea=pa1andb=pb1. Then (a1,b1) = 1 by Exercise 1.2.16. Then (a2,b2) =(p2a12,p2b12) =p2(a12,b12), using Exercise 1.2.18. By the Claim we conclude that (a2,b2) =p2.The choicesp= 2,a=b= 0,c=d= 1 provide a counterexample to (a) and (b).(c) Sincep| (a2+b2) –a.a =b2, conclude thatp|bby Theorem 1.8.Sincen> 1 Theorem 1.10 implies thatnequals a product of primes. We can pull out minus signsto see that n =p1p2…prwhere eachpjis a positive prime. Re-ordering these primes if necessary,to assumep1≤p2≤…≤pr. For the uniqueness, suppose there is another factorizationn=q1q2…qsfor some positive primes qjwithq1≤q2…≤qs. By theorem 1.11 we know thatr=sand thepj’sare just a re-arrangement of theqjs. Thenp1is the smallest of thepj’s, so it also equals thesmallest of theqj’s and thereforep1=q1. We can argue similarly thatp2=q2, …,pr=qr. (Thislast step should really be done by a formal proof invoking the Well Ordering Axiom.)

Abstract Algebra : An Introduction, 3rd Edition Solution Manual - Page 11 preview image

Loading page ...

Arithmetic inZRevisited25. The binomial coefficient(pk)is(pk)=p!k!(p−k)! =p·(p−1)· · ·(p−k+ 1)k(k−1)· · ·1.Now, the numerator is clearly divisible byp. The denominator, however, consists of a product ofintegers all of which are less thanp. Sincepis prime, none of those integers (except 1) dividep,so the product cannot have a factor ofp(to make this more precise, you may wish to write thedenominator as a product of primes and note thatpcannot appear in the list).26.27.24. This is almost identical to the previous exercise. Ifn >0 is an integer, supposea=pr11pr22. . . prkkandb=ps11ps22. . . pskkwhere thepiare distinct positive primes andri≥0,si≥0.Thenan=pnr11pnr22. . . pnrkkandb2=pns11pns22. . . pnskk.Then using Exercise 19 (twice), we havea|bif andonly ifri≤sifor eachiif and only ifnri≤nsifor eachiif and only ifan|bn.822.23. Supposea=pr11pr22. . . prkkandb=ps11ps22. . . pskkwhere thepiare distinct positive primes andri≥0,si≥0. Thena2=p2r11p2r22. . . p2rkkandb2=p2s11p2s22. . . p2skk. Then using Exercise 19 (twice), wehavea|bif and only ifri≤sifor eachiif and only if 2ri≤2sifor eachiif and only ifa2|b2.20.21.(a) The positive divisors of a are the numbersd=p1m1p2m2…pkmkwhere the exponentsmjsatisfy 0≤mj≤rjfor eachj= 1, 2,,..,k. This follows from unique factorization. Ifdalsodividesbwe have 0≤mj≤sjfor eachi= 1, 2,...k. Sincenj= min{rj,sj} we see that thepositive common divisors ofaandbare exactly those numbersd=p1m1p2m2…pkmkwhere0≤mj≤njfor eachj= 1, 2,...,k. Then (a,b) is the largest among these commondivisors, so it equalsp1n1p2n2…pknk.(b) For [a,b] a similar argument can be given, or we can apply Exercise 1.2.31, noting thatmax{r,s} =r+s– min{r,s} for any positive numbersr,s.Answered in the text.If everyriis even it is easy to see thatnis a perfect square. Conversely supposenis a square.First consider the special casen=pris a power of a prime. Ifpr=m2is a square, consider theprime factorization of m. By the uniqueness (Theorem 1.11),pis the only prime that can occur,so m =psfor some s, andpr=m2=p2s. Thenr= 2s'is even. Now for the general case, supposen=m2isaperfect square. If someriis odd, expressn=piri.kwherekis the product of theother primes involved inn.Thenpiriandkare relatively prime and Exercise 13 implies thatpiriis a perfect square. By thespecial case,ri. is even.Claim: EachAk= (n+ 1)! +kis composite, fork= 2, 3,. .. ,n+ 1. Proof. Sincek≤n+havek| (n+ 1)! and thereforek|Ak. ThenAkis composite sinceI<k<Ak.12k+ 3 is a multiple of 3. Similarly ifp= 6k+ 5 thenp2+2 = 36k2+ 60k+ 27 is a multiple of3. So in each case,p2+ 2 is composite.By the division algorithmp= 6k+rwhere 0≤r< 6. Sincep> 3 is prime it is not divisible by 2or 3, and we must haver= 1 or 5. Ifp= 6k+ 1 thenp2= 36k2+ 12k+ 1 andp2+ 2 = 36k2+1 we

Abstract Algebra : An Introduction, 3rd Edition Solution Manual - Page 12 preview image

Loading page ...

33. Supposenis composite, and writen=rswhere 1< r, s < n. Then, as you can see by multiplyingit out,2n−1 = (2r−1)(2s(r−1)+ 2s(r−2)+ 2s(r−3)+· · ·+ 2s+ 1).Sincer >1, it follows that 2r>1. Sinces >1, we see that 2s+ 1>1, so that the second factormust also be greater than 1. So 2n−1 has been written as the product of two integers greater thanone, so it cannot be prime.34.35.36.91.3 Primes and Unique Factorization31.32.30.29.This assertion follows immediately from the Fundamental Theorem 1.11.(b)If2is rational it can be expressed as a fractionabfor some positive integers a, b.Clearing denominators and squaring leads to:a2= 2b2, 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 listp1,p2,…,pkand considerN=p1p2…pk+ 1. Noneof thesepjcan divideN(since 1 can be expressed as a linear combination ofpjandN). ButN> 1soNmust have some prime factorp. (Theorem 1.10). Thispis a prime number not equal to anyof the primes in our list, contrary to hypothesis.Proof: Sincen> 2 we know thatn! – 1 > 1 so it has some prime factorp. Ifp≤nthenp|n!,contrary to the fact thatp|nn<p<n!.We sketch the proof (b). Supposea> 0 (What ifa< 0?),rn=aandr=u/vwhereu,vareintegers andv> 0. Thenun=avu. Ifpis a prime letkbe the exponent ofpoccurring in a (thatis:pk|aand1|kpa+). The exponents ofpoccurring inunand invnmust be multiples ofn, sounique factorization implieskis a multiple ofn. Putting all the primes together we conclude thata=bnfor some integerb.Ifpisaprime > 3 then 2|pand 3|p, so by Exercise 1.2.34 we know 24 |p2–1. Similarly 24 |(q2–1) so thatp2–q2= (p2– 1) – (q2– 1) isamultiple of 24.28.The sums in question are: 1 + 2 + 4 + … + 2n. Whenn= 7 the sum is 255 = 3.5.17 and whenn= 8 the sum is 511 = 7.73. Therefore the assertion is false. The interested reader can verify thatthis sum equals 2n+1– 1. These numbers are related to the“Mersenne primes”.(a) Ifa2= 2b2for positive integers a, b, compare the prime factorizations on both sides. Thepower of 2 occurring in the factorization ofa2must be even (since it isasquare). The powerof 2 occurring in 2b2must be odd. By the uniqueness of factorizations (The FundamentalTheorem) these powers of 2 must be equal,acontradiction.!. Therefore

Abstract Algebra : An Introduction, 3rd Edition Solution Manual - Page 13 preview image

Loading page ...

Abstract Algebra : An Introduction, 3rd Edition Solution Manual - Page 14 preview image

Loading page ...

Chapter 2Congruence inZand ModularArithmetic2.1Congruence and Congruence Classes1.2.3.(a) Computing the checksum gives10·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 gives10·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 ISBNnumber.(c) Computing the checksum gives10·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) 25–1= 24= 16≡1 (mod 5). (b) 47−1=46=4096≡1 (mod 7).(c) 311−1= 310= 590491 (mod 11).(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).≡

Abstract Algebra : An Introduction, 3rd Edition Solution Manual - Page 15 preview image

Loading page ...

4.(a) Computing the checksum gives3·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 gives3·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 gives3·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 Theorem2.2 again) 53≡13(mod 4).Continuing, we get 51000≡11000≡1 (mod 4).Since 51000≡1(mod 4), Theorem 2.3 tells us that[51000]= [1] inZ4.6.7.8.9.10.11.12.13.Congruence inZand Modular Arithmetic12Givenn⎟(a–b) so thata–b=nqfor some integerq. Sincek⎟nit follows thatk⎟(a–b) andthereforea≡b(modk).By Corollary 2.5,a≡0, 1, 2 or 3 (mod 4). Theorem 2.2 impliesa2≡0, 1 (mod 4). Thereforea2cannot be congruent to either 2 or 3 (mod 4).By the division algorithm, any integernis expressible asn= 4q+rwherer∈{0, 1, 2, 3}, andn≡r(mod 4). Ifris 0 or 2 thennis even. Therefore ifnis odd thenn≡1 or 3 (mod 4).(a) (n−a)2≡n2– 2na+a2≡a2(modn) sincen≡0 (modn).(b)(2n−a)2≡4n2– 4na+a2≡a2(mod 4n) since 4n≡0 (mod 4n).Suppose the base ten digits ofaare (cncn–1. . .c1co). (Compare Exercise 1.2.32). Thena=cn10n+cn−10n−1+. . .c110 +c0≡c0(mod 10), since 10k≡0 (mod 10) for everyk≥1.Since there are infinitely many primes (Exercise 1.3.25) there exists a primep>⎪a–b⎪. Byhypothesis,p⎪(a–b) so the only possibility isa–b= 0 anda=b.Ifp≡0, 2 or 4 (mod 6), thenpis divisible by 2. Ifp≡0 or 3 (mod 6) thenpis divisible by 3.Sincepis a prime > 3 these cases cannot occur, so thatp≡1 or 5 (mod 6). By Theorem 2.3 thissays that [p] = [1] or [5] in6.Supposer,r' are the remainders foraandb, respectively. Theorem 2.3 and Corollary 2.5 imply:a≡b(modn) if and only if [a] = [b] if and only if [r] = [r']. Thenr=r'as in the proof of Corollary2.5(2).Z1

Abstract Algebra : An Introduction, 3rd Edition Solution Manual - Page 16 preview image

Loading page ...

14.15.16.17.18.19.20.21.22.2.2Modular Arithmetic1.13(a) Here is one example:a=b= 2 andn= 4.(b) The assertion is: ifn⎪abthen eithern⎪aorn⎪b. This is true whennis prime byTheorem 1.8.Since (a,n) = 1 there exist integersu,vsuch thatau+nv= 1, by Theorem 1.3. Thereforeau≡au+nv≡1 (modn), and we can chooseb=u.Given thata≡1 (modn), we havea=nq+ 1 for some integerq. Then (a,n) must dividea−nq= 1, so (a,n) = 1. One example to see that the converse is false is to usea= 2 andn= 3. Then(a,n) = 1 but [a]≠[1].Since 10≡–1 (mod 11), Theorem 2.2 (repeated) shows that 10n≡(–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] thena≡b(modn) so thata=b+nkfor some integerk. Then (a,n) = (b,n)using Lemma 1.7.(a)One counterexample occurs whena= 0,b= 2 andn= 4.(b)Givena2≡b2(modn), we haven⎪(a2–b2) = (a+b)(a–b). Sincenis prime, useTheorem 1.8 to conclude that eithern⎪(a+b) orn⎪(a−b).Therefore, eithera≡b(modn) ora≡−b(modn).(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= cn10nc110+c0. Thena≡cn+cn-t+ . . .c1+c0(mod 9), since 10k≡1 (mod 9).(a) Here is one example:a= 2,b= 0,c= 2,n= 4.(b) We haven| ab –ac=a(b– c). Since (a,n) = l Theorem 1.5 implies thatn⎪(b–c) andthereforeb≡c(modn).(a) Answered in the text.(b)+012300123112302230133012012300000101232020230321+ . . . +–2.2 Modular Arithmetic

Preview Mode

This document has 206 pages. Sign in to access the full document!

Report

Study Now!

Document Details

Related Documents

Precalculus - Polynomial and Rational Functions

Precalculus - Functions

Precalculus - Exponential and Logarithmic Functions

Math Word Problems - Translating Expressions

Math Word Problems - Equations

Algebra II – Word Problems

Algebra II – Sequences and Series

Algebra II - Segments Lines and Inequalities

Algebra II - Relations and Functions

Algebra II - Rational Expressions

Company

Explore

Study Tools