研FMIS-Ch2-TheoryofDivisibility

1有限域与计算数论FiniteFieldandComputationalNumberTheory张文芳信息科学与技术学院[e-mail]西南交通大学2012级硕/博研究生课程2ZhangWenfangEmail:[e-mail]ence&TechnologySouthwestJiaotongUniversityPart2ElementaryNumberTheory有限域与计算数论FiniteFieldandComputationalNumberTheory3Part2ElementaryNumberTheoryChapter2TheoryofDivisibilityChapter3DistributionofPrimeNumbersChapter4TheoryofCongruencesChapter5ArithmeticofEllipticCurves4Chapter2TheoryofDivisibility2.1BasicConceptsandPropertiesofDivisibility2.2FundamentalTheoremofArithmetic2.3MersennePrimeandFermatNumber2.4Euclid’sAlgorithm2.5ContinuedFraction52.1BasicConceptsandPropertiesofDivisibilityDefinition2.1.1Letaandbbeintegerswithb0.Wesayadivides(整除)b,denotedbya|b,ifthereexistsanintegercsuchthatb=ac.Whenadividesb,wesaythataisadivisor(factor:因子)ofb,andbisamultiple(倍数)ofa.Ifadoesnotdivideb,wewritea∤b.Ifa|band0ab,thenaiscalledaproperdivisor(真因子)ofb.Example2.1.1Theinteger200hasthefollowingpositivedivisors:1,2,4,5,8,10,20,25,40,50,100,200.62.1BasicConceptsandPropertiesofDivisibilityDefinition2.1.2Adivisorofniscalledatrivialdivisorofnifitiseither1ornitself.Adivisorofniscalledanontrivialdivisorofnifitisadivisorofn,butisneither1,norn.Example2.1.2Fortheinteger18,1and18arethetrivialdivisors,whereas2,3,6and9arethenontrivialdivisors.7BasicPropertiesofDivisibilityTheorem2.1.1Leta,bandcbeintegers.(1)Ifa|banda|c,thena|(sb+tc),foranys,tZ.(2)Ifa|b,thena|(bc),foranyintegerc.(3)Ifa|bandb|c,thena|c.Proof.(1)Sincea|banda|c,wehaveb=ma,c=na,m,nZ.Thussb+tc=(sm+tn)a.Hencea|(sb+tc)sincesm+tnisaninteger.8DivisionalgorithmTheorem2.1.2.Foranyintegeraandpositiveintegerb,thereexistuniqueintegersqandrsuchthata=bq+r,0rb,whereaiscalledthedividend(被除数),qthequotient(商),andrtheremainder(余数).9DivisionalgorithmProof.Considerthearithmeticprogression…,3b,2b,b,0,b,2b,3b,…thentheremustbeanintegerqsuchthatqba(q+1)b.Letaqb=r,thena=qb+rwith0rb.Toshowtheuniquenessofqandr,supposethereisanotherpairq1andr1satisfyingthefollowingcondition:a=bq1+r1,0r1b.Wefirstshowthatr1=r.Forifnot,wemaypresumethatrr1,sothat0r1rb,andthenweseethatb(qq1)=r1r,andsob|(r1r),whichisimpossible.Hence,r=r1,andalsoq=q1.10DivisionalgorithmExample2.1.2Letb=15.Then(1)whena=255,a=b·17+0,soq=17andr=015.(2)whena=177,a=b·11+12,soq=11andr=1215.(3)whena=783,a=b·(52)+3,soq=52andr=315.11PrimeDefinition2.1.3.Apositiveintegerngreaterthan1iscalledaprime(素数)ifitsonlydivisorsarenand1.Apositiveintegernthatisgreaterthan1andisnotprimeiscalledcomposite(合数).Theorem2.1.2(Euclid).Thereareinfinitelymanyprime.Proof.Supposethatp1,p2,…,pkarealltheprimes.ConsiderthenumberN=p1p2…pk+1.Ifitisaprime,thenitisanewprime.Otherwise,ithasaprimefactorq.Ifqwereoneoftheprimespi,i=1,2,…,k,thenq|(p1p2…pk),andsinceq|(p1p2…pk+1),qwoulddividethedifferenceofthesenumber,namely1,whichisimpossible.Soqcannotbeoneofthepifori=1,2,…,k,andmustthereforebeanewprime.12PrimeTheorem2.1.3.Ifnisaninteger1,thenthereisaprimepsuchthatnpn!+1.Theorem2.1.4.Givenanyrealnumberx1,thenexistsaprimebetweenxand2x.13TheSieveofEratosthenes（埃拉托色尼筛法）Theorem2.1.5.Ifnisacomposite,thennhasaprimedivisorpsuchthat.pnProof.Letpbethesmallestprimedivisorofn.Ifn=rs,thenprandps.Hence,p2rs.14TheSieveofEratosthenes(筛选法)Algorithm2.1.1.Givenapositiveintegern1,thisalgorithmwillfindallprimesupton.(1)Createalistofintegersfrom2ton:2,3,4,5,6,7,8,9,10,11,12,13,14,15,…,n.(2)Forprimenumberspi(i=1,2,3,…)from2,3,5upto,ndeleteallthemultiplespipimnfromthelist:(2.1)Startingfrom2,deleteallthemultiples2mof2suchthat22mn:2,3,5,7,9,11,13,15,…,n.(2.2)Startingfrom3,deleteallthemultiples3mof3suchthat33mn:2,3,5,7,11,13,…,n.……(3)Printtheintegersremaininginthelist.15TheSieveofEratosthenesExampleLet=37,then376,thereonlythreeprimesn(2.1)deleteallthemultiples2mof2suchthat22m37.2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37.2,3and5below6.(1)Allpositiveintegersfrom2to37areasfollows.2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37.16TheSieveofEratosthenes(2.2)deleteallthemultiples3mof3suchthat33m37.2,3,,5,,7,,9,,11,,13,,15,,17,,19,,21,,23,,25,,27,,29,,31,,33,,35,,37.(2.3)deleteallthemultiples5mof5suchthat55m37.2,3,,5,,7,,,,11,,13,,,,17,,19,,,,23,,25,,,,29,,31,,,,35,,37.(3)Theremainingnumbers2,3,5,7,11,13,17,19,23,29,31,37arethentheprimesupto37.17Chapter2TheoryofDivisibility2.1BasicConceptsandPropertiesofDivisibility2.2FundamentalTheoremofArithmetic2.3MersennePrimeandFermatNumber2.4Euclid’sAlgorithm2.5ContinuedFraction182.2FundamentalTheoremofArithmeticTheorem2.2.1.Everypositiveintegerngreaterthan1canbewrittenuniquelyastheproductofprimes:1212....kaaaknpppwherep1,p2,…,pkaredistinctprimes,anda1,a2,…,akarenaturalnumbers.Example2.2.1.Thefollowingaresomesampleprimefactorizations:643=6432311=2147483647644=22·7·23231+1=3·715827883645=3·5·432321=3·5·17·257·65537646=2·17·19232+1=641·6700417647=647231+2=2·52·13·41·61·132119ThegreatestcommondivisorDefinition2.2.1.Letaandbbeintegers,notbothze