交通大学课程FMIS-Ch2-TheoryofDivisibility有限域与计算数论

交通大学课程FMIS-Ch2-TheoryofDivisibility有限域与计算数论ZhangWenfangEmail:wfzhang@SchoolofInformationScience&Technology

SouthwestJiaotongUniversityPart2ElementaryNumberTheory有限域与计算数论

FiniteFieldandComputational

NumberTheory2Part2ElementaryNumberTheory

Chapter2TheoryofDivisibility

Chapter3DistributionofPrimeNumbersChapter4TheoryofCongruencesChapter5ArithmeticofEllipticCurves3Chapter2TheoryofDivisibility2.1BasicConceptsandPropertiesofDivisibility2.2FundamentalTheoremofArithmetic2.3MersennePrimeandFermatNumber2.4Euclid’sAlgorithm2.5ContinuedFraction42.1BasicConceptsandPropertiesofDivisibilityDefinition2.1.1Letaandbbeintegerswithb

0.Wesaya

divides(整除)b,denotedbya|b,ifthereexistsanintegercsuchthatb=ac.Whenadividesb,wesaythataisadivisor

(factor:因子)ofb,andbisamultiple(倍数)ofa.Ifadoesnotdivideb,wewritea∤b.Ifa|band0<a<b,thenaiscalledaproperdivisor(真因子)ofb.Exle2.1.1Theinteger200hasthefollowingpositivedivisors:1,2,4,5,8,10,20,25,40,50,100,200.52.1BasicConceptsandPropertiesofDivisibilityDefinition2.1.2Adivisorofniscalledatrivialdivisorofnifitiseither1ornitself.Adivisorofniscalledanontrivialdivisorofnifitisadivisorofn,butisneither1,norn.Exle2.1.2Fortheinteger18,1and18arethetrivialdivisors,whereas2,3,6and9arethenontrivialdivisors.6BasicPropertiesofDivisibilityTheorem2.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.7DivisionalgorithmTheorem2.1.2.Foranyintegeraandpositiveintegerb,thereexistuniqueintegersqandrsuchthat

a=bq+r,0

r<b,whereaiscalledthedividend(被除数),qthequotient(商),andrtheremainder(余数).8DivisionalgorithmProof.Considerthearithmeticprogression

…,

3b,2b,

b,0,b,2b,3b,…thentheremustbeanintegerqsuchthatqb

a<(q+1)b.Leta

qb=r,thena=qb+rwith0

r<b.Toshowtheuniquenessofqandr,supposethereisanotherpairq1andr1satisfyingthefollowingcondition:a=bq1+r1,0

r1<b.Wefirstshowthatr1=r.Forifnot,wemaypresumethatr<r1,sothat0<r1

r<b,andthenweseethatb(q

q1)=r1

r,andsob|(r1

r),whichisimpossible.Hence,r=r1,andalsoq=q1.9DivisionalgorithmExle2.1.2Letb=15.Then(1)whena=255,a=b·17+0,soq=17andr=0<15.(2)whena=177,a=b·11+12,soq=11andr=12<15.(3)whena=783,a=b·(52)+3,soq=52andr=3<15.10PrimeDefinition2.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.11PrimeTheorem2.1.3.Ifnisaninteger1,thenthereisaprimep

suchthatn

p

n!+1.Theorem2.1.4.Givenanyrealnumberx1,thenexistsaprimebetween

xand2x.12TheSieveofEratosthenes

（埃拉托色尼筛法）Theorem2.1.5.Ifnisacomposite,thennhasaprimedivisorp

suchthatProof.Letpbethesmallestprimedivisorofn.Ifn=rs,thenp

randp

s.Hence,p2

rs.13TheSieveofEratosthenes(筛选法)Algorithm2.1.1.Givenapositiveintegern>1,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

deleteallthemultiplespi<pi

m

nfromthelist:

(2.1)Startingfrom2,deleteallthemultiples2mof2suchthat2<2m

n:2,3,5,7,9,11,13,15,…,n.(2.2)Startingfrom3,deleteallthemultiples3mof3suchthat3<3m

n:2,3,5,7,11,13,…,n.……(3)Printtheintegersremaininginthelist.14TheSieveofEratosthenesExample

(2.1)deleteallthemultiples2mof2suchthat2<2m

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.15TheSieveofEratosthenes

(2.2)deleteallthemultiples3mof3suchthat3<3m

37.2,3,,5,,7,,9,,11,,13,,15,,17,,19,,21,,23,,25,,27,,29,,31,,33,,35,,37.(2.3)deleteallthemultiples5mof5suchthat5<5m

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.16Chapter2TheoryofDivisibility2.1BasicConceptsandPropertiesofDivisibility2.2FundamentalTheoremofArithmetic2.3MersennePrimeandFermatNumber2.4Euclid’sAlgorithm2.5ContinuedFraction172.2FundamentalTheoremofArithmeticTheorem2.2.1.Everypositiveintegerngreaterthan1canbewrittenuniquelyastheproductofprimes:

wherep1,p2,…,pkaredistinctprimes,anda1,a2,…,akarenaturalnumbers.Exle2.2.1.Thefollowingaresomesleprimefactorizations:643=6432311=2147483647644=22·7·23231+1=3·715827883645=3·5·432321=3·5·17·257·65537646=2·17·19232+1=641·6700417647=647231+2=2·52·13·41·61·132118ThegreatestcommondivisorDefinition2.2.1.Letaandbbeintegers,notbothzero.Thelargest

divisordsuchthatd|aandd|biscalledthegreatestcommondivisor(gcd:最大公因子)ofaandb.Thegreatestcommondivisorofaandbisdenotedbygcd(a,b).Exle2.2.2.Thesetofpositivedivisorof111and333areasfollows:1,3,37,111,1,3,9,37,111,333,sogcd(111,333)=111.Butgcd(91,111)=1,since91and111havenocommondivisorsotherthan1.19ThegreatestcommondivisorTheorem2.2.2.Letaandbbeintegers,notbothzero.Thenthereexistsintegersxandysuchthat

d=gcd(a,b)=ax+by.

Proof.Considerthesetofalllinearcombinationsau+bv,whereuandvrangeoverallintegers.Clearlythissetofintegers{au+bv}includespositive,negativeaswellas0.Choosexandysuchthatm=ax+byisthesmallestpositiveintegerintheset.UsetheDivisoralgorithm,towritea=mq+r,where0

r<m.Then

r=a

mq=a

q(ax+by)=(1qx)a+(qy)bandhencerisalsoalinearcombinationofaandb.Butr<m,soitfollowsfromthedefinitionofmthatr=0.Thusa=mq,thatism|a;similarly,m|b.Therefore,misacommondivisorofaandb.Sinced=gcd(a,b),m

d.Sinced|aandd|b,thend|m,d

m.Thus,wemusthaved=m.20RelativelyprimeDefinition2.2.2.Twointegersaandbarecalledrelativelyprime(互素)ifgcd(a,b)=1.Wesaythatintegersa1,a2,…,akarepairwiserelativelyprimeif,wheneveri

j,wehavegcd(ai,aj)=1.Exle2.2.3.91and111arerelativelyprime,sincegcd(91,111)=1.21RelativelyprimeProof.Ifaandbarerelativelyprime,sothatgcd(a,b)=1,thenTheorem2.2.2guaranteestheexistenceofintegersxandysatisfyingax+by=1.Asfortheconverse,supposethatax+by=1andthatgcd(a,b)=d.Sinced|aandd|b,d|(ax+by),thatd|1.Thusd=1.Theorem2.2.3.Letaandbbeintegers,notbothzero,thenaandbarerelativelyprimeifandonlyifthereexistsintegersxandysuchthatax+by=1.22RelativelyprimeProof.ByTheorem2.2.2,wecanwriteax+by=1forsomechoiceofintegersxandy.Multiplyingthisequationbycwegetacx+bcy=c.Sincea|acanda|bc,itfollowingthata|(acx+bcy).Thatisa|c.Theorem2.2.4.Ifa|bcandgcd(a,b)=1,thena|c.23Theleastcommonmultiple(LCM)Ifdisamultipleofaandalsoamultipleofb,thendisacommonmultipleofaandb.Theleastcommonmultiple(lcm:最小公倍数)oftwointegersaandb,isthesmallestcommonmultipleofaandb.Theleastcommonmultipleofaandbisdenotedbylcm(a,b).Theorem2.2.5.If24Theleastcommonmultiple(LCM)Theorem2.2.6.Supposeaandbarepositiveintegers,thenExle2.2.3.Findgcd(240,560)andlcm(240,560).25Chapter2TheoryofDivisibility2.1BasicConceptsandPropertiesofDivisibility2.2FundamentalTheoremofArithmetic2.3MersennePrimeandFermatNumber2.4Euclid’sAlgorithm2.5ContinuedFraction

26MersenneprimeDefinition2.3.1.AnumberiscalledaMersennenumberifitisintheformof

Mp=2p

1,wherepisaprime.IfaMersennenumberisaprime,thenaitiscalledaMersenneprime.Exle2.3.1.Thefollowingnumbers221=3,231=7,251=31,271=127,2131=8191,2171=131071.areallMersennenumbersaswellasMersenneprimes,but2111isonlyaMersennenumbers,notaMersenneprimes,since2111=2047=2389isacomposite.27MersenneprimeTheknownMersenneprimes

Mp=2p

1No.pDigitsinMpdiscoverer(s)andtime1215134Anonymous,14566176Cataldi,158883110Euler,177296119Pervushin,1883108927Powers,191125217016533Nool&Nickell(two18-year-oldAmericanhigh-choolstudentsinCalifornia),19783869725932098960Hajratwala,Woltman&Kurowskietal.,1999391346691740533946Cameron,Woltman&Kurowskietal.,200128FermatnumberDefinition2.3.2.NumbersoftheformFermatwaswrongFermatin1640conjectured,inalettertoMersenne,thatallFermatnumberwereprimesafterhehadverifieditupton=4;butEulerin1732foundthatthefifthFermatnumberisnotaprime,sinceF5=6416700417.

Todate,theFermatnumbersF5,F6,…,F11havebeencompletelyfactored.

calledFermatnumber.AFermatnumberiscalledaprimeFermatnumberifitisprime.AFermatnumberiscalledacompositeFermatnumberifitiscomposite.29Chapter2TheoryofDivisibility2.1BasicConceptsandPropertiesofDivisibility2.2FundamentalTheoremofArithmetic2.3MersennePrimeandFermatNumber2.4Euclid’sAlgorithm2.5ContinuedFraction302.4Euclid’sAlgorithmProof.LetX=gcd(a,b)andY=gcd(b,r),itsufficestoshowX=Y.Ifintegercisadivisorofaandb,itfollowsfromtheequationa=bq+randthedivisibilitypropertiesthatcisadivisorofralso.Bythesameargument,everycommondivisorofbandrisadivisorofa.Theorem2.4.1.Leta,b,q,rbeintegerswithb>0and0

r<bsuchthata=bq+r.Thengcd(a,b)=gcd(b,r).312.4Euclid’sAlgorithm

Then(1)gcd(a,b)=rn.Theorem2.4.2.Letaandbbepositiveintegerswitha>b.Applythedivisionalgorithmrepeatedlyasfollows:322.4Euclid’sAlgorithm

(2)Valuesofxandyingcd(a,b)=ax+by=rncanbeobtainedbywritingeachriasalinearcombinationofaandb.

rn=rn

2

rn1

qn

1=…=ax+by.332.4Euclid’sAlgorithmRemark2.4.1.Euclid’salgorithmisfoundinBookVII,Proposition1and2ofhisElements(几何原本),butitprobablywasn’thisowninvention.Scholarsbelievethatthemethodwasknownupto200yearsearlier.However,itfirstappearedinEuclid’sElements,andmoreimportantly,itisfirstnontrivialalgorithmthathassurvivedtothisday.Remark2.4.2.IfEuclid’salgorithmisappliedtotwopositiveintegersaandbwitha>b,thenthenumberofdivisionsrequiredtofindgcd(a,b)isO(logb),apolynomial-timecomplexity.Thebig-Onotationisusedtodenotetheupperboundofacomplexityfunction,i.e.,f(n)=O(g(n))ifthereexistssomeconstantc>0suchthatf(n)

c

g(n).342.4Euclid’sAlgorithmExle2.4.1.UseEuclid’salgorithmtofindthegcdof1281and243.Since1281=2435+66,243=663+45,66=451+21,45=212+3,21=37+0,wehavegcd(1281,243)=3,and