欢迎来到天天文库
浏览记录
ID:14363112
大小:464.56 KB
页数:117页
时间:2018-07-28
《elementary number theory and primality tests》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、Chapter1TheFundamentalTheoremofArithmetic1.1PrimenumbersIfa;b2Zwesaythatadividesb(orisadivisorofb)andwewriteajb,ifb=acforsomec2Z.Thus 2j0but0-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=p1p2pn+1:Evidentlynoneoftheprimesp1;:::;pndividesN.Lemma1.1Everynaturalnumbern>1hasatleastoneprimedivisor.ProofofLemmaBThesmallestdivisord>1ofnmustbeprime.Forotherwisedwouldhaveadivisorewith15、hasaprimefactorp,whichdiffersfromp1;:::;pn.JOurargumentnotonlyshowsthatthereareaninfinityofprimes;itshowsthat2npn<2;averyfeeblebound,butourown.Toseethis,wearguebyinduction.Ourproofshowsthatpn+1p1p2pn+1:Butnow,byourinductivehypothesis,21222np1<2;p2<2;:::;pn<2:Itfollowsthatp221+22+6、+2nn+1But12nn+1n+12+2++2=2 1<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]>y 12yandso,settingx=2,(x)log2log2x 1>loglogx 1:forx>1.(Wefollowtheusualconventionthatifnobaseisgiventhenlogxdenotesthelogarithmofxtobasee.)ThePrimeNumberTheorem(whichweshallmakenoattempttoprove)as
5、hasaprimefactorp,whichdiffersfromp1;:::;pn.JOurargumentnotonlyshowsthatthereareaninfinityofprimes;itshowsthat2npn<2;averyfeeblebound,butourown.Toseethis,wearguebyinduction.Ourproofshowsthatpn+1p1p2pn+1:Butnow,byourinductivehypothesis,21222np1<2;p2<2;:::;pn<2:Itfollowsthatp221+22+
6、+2nn+1But12nn+1n+12+2++2=2 1<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]>y 12yandso,settingx=2,(x)log2log2x 1>loglogx 1:forx>1.(Wefollowtheusualconventionthatifnobaseisgiventhenlogxdenotesthelogarithmofxtobasee.)ThePrimeNumberTheorem(whichweshallmakenoattempttoprove)as
此文档下载收益归作者所有