Algebra and number theory - Baker A.

Algebra&NumberTheory[13/05/2003]A.BakerDepartmentofMathematics,UniversityofGlasgow.E-mailaddress:[e-mail]:»ajbContentsChapter1.BasicNumberTheory11.Thenaturalnumbers12.Theintegers33.TheEuclideanAlgorithmandthemethodofback-substitution44.Thetabularmethod65.Congruences86.Primesandfactorization117.Congruencesmoduloaprime138.Finitecontinuedfractions169.Infinitecontinuedfractions1710.Diophantineequations2211.Pell’sequation23ProblemSet125Chapter2.Groupsandgroupactions291.Groups292.Permutationgroups303.Thesignofapermutation314.Thecycletypeofapermutation325.Symmetrygroups336.SubgroupsandLagrange’sTheorem357.Groupactions38ProblemSet243Chapter3.Arithmeticfunctions471.Definitionandexamplesofarithmeticfunctions472.ConvolutionandM¨obiusInversion48ProblemSet352Chapter4.Finiteandinfinitesets,cardinalityandcountability531.Finitesetsandcardinality532.Infinitesets553.Countablesets554.Powersetsandtheircardinality575.Therealnumbersareuncountable59ProblemSet460Index611CHAPTER1BasicNumberTheory1.ThenaturalnumbersThenaturalnumbers0;1;2;:::formthemostbasictypeofnumberandarisewhencountingelementsoffinitesets.WedenotethesetofallnaturalnumbersbyN0=f0;1;2;3;4;:::gandnowadaysthisisverystandardnotation.Itisperhapsworthremarkingthatsomepeopleexclude0fromthenaturalnumbersbutwewillincludeitsincetheemptyset;has0elements!WewillusethenotationZ+forthesetofallpositivenaturalnumbersZ+=fn2N0:n6=0g=f1;2;3;4;:::g;whichisalsooftendenotedN,althoughsomeauthorsalsousethistodenoteourN0.Wecanaddandmultiplynaturalnumberstoobtainnewones,i.e.,ifa;b2N0,thena+b2N0andab2N0.Ofcoursewehavethefamiliarpropertiesoftheseoperationssuchasa+b=b+a;ab=ba;a+0=a=0+a;a1=a=1a;a0=0=0a;etc:Wecanalsocomparenaturalnumbersusinginequalities.Givenx;y2N0exactlyoneofthefollowingmustbetrue:x=y;xy;yx:Asusual,ifoneofx=yorxyholdsthenwewritex6yoryx.Inequalityistransitiveinthesensethatxyandyz=)xz:Themostsubtleaspectofthenaturalnumberstodealwithisthefactthattheyformaninfiniteset.WecanandusuallydolisttheelementsofN0inthesequence0;1;2;3;4;:::whichneverends.OneofthemostimportantpropertiesofN0isTheWellOrderingPrinciple(WOP):Everynon-emptysubsetSµN0containsaleastelement.AleastorminimalelementofasubsetSµN0isanelements02Sforwhichs06sforalls2S.Similarly,agreatestormaximalelementofSisoneforwhichs6s0foralls2S.NoticethatN0hasaleastelement0,buthasnogreatestelementsinceforeachn2N0,n+12N0andnn+1.Itiseasytoseethatleastandgreatestelements(iftheyexist)arealwaysunique.Infact,WOPislogicallyequivalenttoeachofthetwofollowingstatements.ThePrincipleofMathematicalInduction(PMI):Supposethatforeachn2N0thestatementP(n)isdefinedandalsothefollowingconditionshold:²P(0)istrue;²wheneverP(k)istruethenP(k+1)istrue.121.BASICNUMBERTHEORYThenP(n)istrueforalln2N0.TheMaximalPrinciple(MP):LetTµN0beanon-emptysubsetwhichisboundedabove,i.e.,thereexistsab2N0suchthatforallt2T,t6b.ThenTcontainsagreatestelement.Itiseasilyseenthattwogreatestelementsmustagreeandwethereforerefertothegreatestelement.Theorem1.1.ThefollowingchainofimplicationsholdsPMI=)WOP=)MP=)PMI:Hencethesethreestatementsarelogicallyequivalent.Proof.PMI=)WOP:LetSµN0andsupposethatShasnoleastelement.WewillshowthatS=;.LetP(n)bethestatementP(n):k=2Sforallnaturalnumbersksuchthat06k6n.Noticethat0=2SsinceitwouldbealeastelementofS.HenceP(0)istrue.NowsupposethatP(n)istrue.Ifn+12S,thensincek=2Sfor06k6n,n+1wouldbetheleastelementofS,contradictingourassumption.Hence,n+1=2SandsoP(n+1)istrue.BythePMI,P(n)istrueforalln2N0.Inparticular,thismeansthatn=2SforallnandsoS=;.WOP=)MP:LetTµN0haveupperboundbandsetS=fs2N0:tsforallt2Tg:ThenSisnon-emptysincefort2T,t6bb+1;sob+12S.Ifs0isaleastelementofS,thentheremustbeanelementt02Tsuchthats0¡16t0;butwealsohavet0s0.Combiningtheseweseethats0¡1=t02T.Noticealsothatforeveryt2T,ts0,hencet6s0¡1.Thust0isthedesiredgreatestelement.MP=)PMI:LetP(n)beastatementforeachn2N0.SupposethatP(0)istrueandforn2N0,P(n)=)P(n+1).Supposethatthereisanm2N0forwhichP(m)isfalse.ConsiderthesetT=ft2N0:P(n)istrueforallnaturalnumbersnsatisfying06n6tg:NoticethatTisboundedabovebym,sinceifm6k,k=2T.Lett0bethegreatestelementofT,whichexiststhankstotheMP.ThenP(t0)istruebydefinitionofT,hencebyassumptionP(t0+1)isalsotrue.ButthenP(n)istruewhenever06n6t0+1,hencet0+12T,contradictingthefactthatt0wasthegreatestelementofT.Hence,P(n)mustbetrueforalln2N0.¤Animportantapplicationoftheseequivalentresultsistoprovingthefollowingpropertyofthenaturalnumbers.Theorem1.2(LongDivisionProperty).Letn;d2N0with0d.Thenthereareuniquenaturalnumbersq;r2N0satisfyingthetwoconditionsn=qd+rand06rd.Proof.ConsiderthesetT=ft2N0:td6ngµN0:2.THEINTEGERS3ThenTisnon-emptysince02T.Also,fort2T,t6td,hencet6n.SoTisboundedabovebynandhencehasagreatestelementq.Butthenqd6n(q+1)d.Noticethatifr=n¡qd,then06r=n¡qd(q+1)d¡qd=d:Toproveuniqueness,supposethatq0;r0isasecondsuchpair.Supposethatr6=r0.Byinterchangingthepairsifnecessary,wecanassumethatrr0.Sincen=qd+r=q0d+r0,0r0¡r=(q¡q0)d:Noticethatthismeansq06qsinced0.Ifqq0,thisimpliesd6(q¡q0)d,henced6r0¡rd¡r6d;andsoddwhichisimpossible.Soq=q0whichimpli