Hungerford-抽象代数-华盛顿大学课程-题解和讲义

Math402AAutumn1998SolutionsforWeek1HomeworkSection1.12Supposewewanttodivideabyb;thatis,wewanttondq;rsothata=bq+rwith0rb.Divideabybonyourcalculator.Iftheanswerispositive,qisthenumbertotheleftofthedecimalpoint.Iftheanswerisnegative,qisonelessthanthenumbertotheleftofthedecimalpoint.(Ineithercase,qisthesmallestintegerlessthanorequaltothenumberdisplayedonyourcalculator.)Thenndrbycomputingabq.3(d)Theresultonthecalculatorofdividing8126493by541is15021:243,soq=15021,andr=(8126493)(541)(15021)=132.6Letabeanoddinteger.Bythedivisionalgorithm,weseethata=4k+rwhere0r4.Therearefourcases:(0)a=4k+0.Thena=2(2k)+0andaiseven.(1)a=4k+1.Thena=2(2k)+1andaisodd.(2)a=4k+2.Thena=2(2k+1)+0andaiseven.(3)a=4k+3.Thena=2(2k+1)+1andaisodd.8(a)52=25=4(6)+172=49=4(12)+1112=121=4(30)+1152=225=4(56)+1272=729=4(182)+1(b)Theremainderwhenthesquareofanoddintegerisdividedby8is1.Equivalently,ifaisanoddinteger,thena2=8q+1forsomeintegerq.(c)Byproblem6above,ifaisanoddinteger,theneithera=4k+1ora=4k+3forsomeintegerk.Sotherearetwocases:(1)a=4k+1.Thena2=16k2+8k+1=8(2k2+k)+1.(3)a=4k+3.Thena2=16k2+24k+9=8(2k2+3k+1)+1.Section1.21(e)Div(306)=f1;2;3;6;9;17;18;34;51;102;153;306gDiv(657)=f1;3;9;73;219;657gHence(306;657)=9.6Sinceajb,thereexistsanintegermsothatb=am.Sincecjd,thereexistsanintegernsothatd=cn.Butthenbd=(am)(cn)=(ac)(mn),andthusacjbd.11(a)Weclaimthatifd2,thendisnotacommondivisorofnandn+2.Supposed2anddjn.Thenn=dqforsomeintegerq.Butthen,n+2=dq+2,sobythedivisionalgorithm,d6jn+2.Hencethegreatestcommondivisorofnandn+2mustbelessthanorequalto2.Bothpossibleanswers(1and2)arepossible:forexample,(3;5)=1and(2;4)=2.(b)Byasimilarargumentasabove,thegreatestcommondivisorofnandn+6mustbelessthanorequalto6.But4cannotbeacommondivisor:if4jn,thenn=4qforsomeintegerq,andn+6=4q+6=4(q+1)+2,so46jn+6.Similarly,5cannotbeacommondivisor:if5jn,thenn=5qforsomeintegerq,andn+6=5q+6=5(q+1)+1,so56jn+6.Sothepossiblecommondivisorsofnandn+6aref1;2;3;6g,andallarepossible:(5;11)=1,(4;10)=2,(3;9)=3,(6;12)=6.12(a)False:seta=2;b=3.Then(2;3)=1but(6;3)=3.(b)False:seta=2;b=3;c=3.Then(2;3)=1,(2;3)=1,but(3;3)=3.1(c)True:If(a;b)=1thenthereexistintegersm;nsuchthatam+bn=1:Similarlyif(a;c)=1thenthereexistintegersu;vsuchthatau+cv=1:Multiplyingtheabovestatementstogethergives(am+bn)(au+cv)=1whichcanbefactoredasa(amu+mcv+ubn)+bc(nv)=1andhence(a;bc)=1.(d)False:seta=2;b=3;c=3.Then(2;3)=1,(2;3)=1,but(6;3)=3.2Math402AAutumn1998SolutionsforWeek2HomeworkSection1.223Supposedisacommondivisorofaand(b;c).Thendjaanddj(b;c).Butthendjbanddjc,sodj(a;b)aswell.Hencedisacommondivisorof(a;b)andc.Asimilararugmentshowsthatifdisacommondivisorof(a;b)andc,thendisalsoacommondivisorofaand(b;c).Thusaand(b;c)havethesamecommondivisorsas(a;b)andc,andthushavethesamegreatestcommondivisor.24If(a;c)=1thenau+cv=1forsomeu;v.Similarlyif(b;c)=1thenbm+cn=1forsomem;n.Multiplyingthesetwostatmentstogethergives(au+cv)(bm+cn)=1whichexpandstoab(um)+c(vbm+aun+cvn)=1andhence(ab;c)=1.34(a)Ifdjaanddjb,thendj(a+b)anddj(ab).Henceanycommondivisorofaandbisalsoacommondivisorofa+bandab,andhence(a;b)j(a+b;ab).(b)(c)Letd=(a;b)ande=(a+b;ab).Thentheaboveshowsthatdje,andasimilarargumentshowsthatej((a+b)+(ab);(a+b)(ab)),thatisej(2a;2b).But(2a;2b)=2(a;b),soej2d.Henceeithere=dore=2d.Ifaisoddandbiseven,thendandemustbothbeodd(since26ja),henced=e.Ifaandbarebothodd,thendisodd(since26ja),buteiseven(since2j(a+b)and2j(ab)),soe=2d.Section1.36Yes:supposepjan.Factora=p1pkintoaproductofprimes.Thenan=pn1pnk,andhencepjpniforsomei.Butthismeansthatp=pi,sopn=pniandhencepnjan.Note:theresultisnottrueforcompositenumbers(example:4j22but426j22).9Suppose(a;b)=p.Thena=pmandb=pnwith(m;n)=1.Thena2=p2m2andb2=p2n2.But(m2;n2)=1still(checkthis!),so(a;b)=p2.12(a)Suppose3ja2+b2.By1:1#5,weknowthateithera2=3kora2=3k+1.Similarlyb2=3lorb2=3l+1.Inanycaseotherthana2=3kandb2=3l,wehavea2+b2=3(k+l)+f1or2g,andhence36j(a2+b2).Thus3ja2and3jb2,andthus3jaand3jb(byTheorem1.8).(b)Byasimilarargumentto1.1#5,wecanseethateithera2=5k,a2=5k+1ora2=5k+4,andthesameforb2andc2.Ifnoneofthemweremultiplesof5,thenwewouldhavea2+b2+c2=5p+f3;6;9;or12g(e.g.wewouldget3ifallwereoftheform5k+1,wewouldget6iftwowereoftheform5k+1andthethirdwereoftheform5k+4,etc.),andhence56j(a2+b2+c2).20(a)Writea=2n1pn22pnkkwithallthepi2fori1,andwriteb=2m1qm22qmllwithalltheqj2forj1.Thena2=22n1p2n22p2nkkand2b2=22m1+1q2m22q2mllsotheycannotbeequalbecausetheprimefactorizationofa2hasanevenpowerof2,whereastheprimefactorizationof2b2hasanoddpowerof2.(b)Supposep2=a=bforsomeintegersa;b.Thenp2b=a,andhence,squaringbothsides,2b2=a2.Butthiscontradictspart(a)above.1Section2.15Ifab(modn),thennj(ab).Butthenn2j(ab)2,whichisn2j(a2+b22ab).Soa2+b22ab(modn2).8(a)251=24=16,and5j(161).(b)471=46=4096,and7j(40961).(c)3111=310=59049,and11j(590491).11(a)Onecancheckthattheonlysolutionwith0x5isx=4.Thusx2[4](mod5)arethesolutions.(b)Onecancheckthattheonlysolutionwith0x7isx=5.Thusx2[5](mod7)arethesolutions.(c)Onecancheckthattheonlysolutionswith0x15arex=3;8;13.Thusx2[4][[9][[14](mod15)arethesolutions,whichisequivalentt