elementary number theory and primality tests

《elementary number theory and primality tests》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、Chapter1TheFundamentalTheoremofArithmetic1.1PrimenumbersIfa;b2Zwesaythatadividesb(orisadivisorofb)andwewriteajb,ifb=acforsomec2Z.Thus2j0but0-2.Definition1.1Thenumberp2Nissaidtobeprimeifphasjust2divisorsinN,namely1anditself.Notethatourdefinitionexcludes0(whichhasaninfinityofdivisorsinN)an

2、d1(whichhasjustone).Writingouttheprimenumbersinincreasingorder,weobtainthesequenceofprimes2;3;5;7;11;13;17;19;:::whichhasfascinatedmathematicianssincetheancientGreeks,andwhichisthemainobjectofourstudy.Definition1.2Wedenotethenthprimebypn.Thusp5=11;p100=541.Itisconvenienttointroduceakind

3、ofinversefunctiontopn.Definition1.3Ifx2Rwedenoteby(x)thenumberofprimesx:(x)=kfpx:pprimegk:Thus(1:3)=0;(3:7)=2:Evidently(x)ismonotoneincreasing,butdiscontinuouswithjumpsateachprimex=p.1–13741–2Theorem1.1(Euclid’sFirstTheorem)Thenumberofprimesisinfinite.ProofISupposetherewereonlyafin

4、itenumberofprimes,sayp1;p2;:::;pn:LetN=p1p2


pn+1:Evidentlynoneoftheprimesp1;:::;pndividesN.Lemma1.1Everynaturalnumbern>1hasatleastoneprimedivisor.ProofofLemmaBThesmallestdivisord>1ofnmustbeprime.Forotherwisedwouldhaveadivisorewith1

5、hasaprimefactorp,whichdiffersfromp1;:::;pn.JOurargumentnotonlyshowsthatthereareaninfinityofprimes;itshowsthat2npn<2;averyfeeblebound,butourown.Toseethis,wearguebyinduction.Ourproofshowsthatpn+1p1p2


pn+1:Butnow,byourinductivehypothesis,21222np1<2;p2<2;:::;pn<2:Itfollowsthatp221+22+

6、
+2nn+1But12nn+1n+12+2+


+2=21<2:Hence2n+1pn+1<2:Itfollowsbyinductionthat2npn<2;foralln1,theresultbeingtrivialforn=1.Thisisnotaverystrongresult,aswesaid.Itshows,forexample,thatthe5thprime,infact11,is2532<2=2=4294967296:Ingeneral,anyboundforpngivesaboundfor(x)intheoppositedirection,

7、andviceversa;forpnx()(x)n:3741–3Inthepresentcase,forexample,wededucethat2y(2)[y]>y12yandso,settingx=2,(x)log2log2x1>loglogx1:forx>1.(Wefollowtheusualconventionthatifnobaseisgiventhenlogxdenotesthelogarithmofxtobasee.)ThePrimeNumberTheorem(whichweshallmakenoattempttoprove)as