研FMIS-Ch2-TheoryofDivisibility

《研FMIS-Ch2-TheoryofDivisibility》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、有限域与计算数论FiniteFieldandComputationalNumberTheory张文芳信息科学与技术学院wfzhang@swjtu.edu.cn西南交通大学2012级硕/博研究生课程1ZhangWenfangEmail:wfzhang@swjtu.edu.cnSchoolofInformationScience&TechnologySouthwestJiaotongUniversityPart2ElementaryNumberTheory有限域与计算数论FiniteFieldandComputationa

2、lNumberTheory2Part2ElementaryNumberTheoryChapter2TheoryofDivisibilityChapter3DistributionofPrimeNumbersChapter4TheoryofCongruencesChapter5ArithmeticofEllipticCurves3Chapter2TheoryofDivisibility2.1BasicConceptsandPropertiesofDivisibility2.2FundamentalTheoremofAri

3、thmetic2.3MersennePrimeandFermatNumber2.4Euclid’sAlgorithm2.5ContinuedFraction42.1BasicConceptsandPropertiesofDivisibilityDefinition2.1.1Letaandbbeintegerswithb0.Wesayadivides(整除)b,denotedbya

4、b,ifthereexistsanintegercsuchthatb=ac.Whenadividesb,wesaythataisadivis

5、or(factor:因子)ofb,andbisamultiple(倍数)ofa.Ifadoesnotdivideb,wewritea∤b.Ifa

6、band0

7、2.1.2Adivisorofniscalledatrivialdivisorofnifitiseither1ornitself.Adivisorofniscalledanontrivialdivisorofnifitisadivisorofn,butisneither1,norn.Example2.1.2Fortheinteger18,1and18arethetrivialdivisors,whereas2,3,6and9arethenontrivialdivisors.6BasicPropertiesofDivisi

8、bilityTheorem2.1.1Leta,bandcbeintegers.(1)Ifa

9、banda

10、c,thena

11、(sb+tc),foranys,tZ.(2)Ifa

12、b,thena

13、(bc),foranyintegerc.(3)Ifa

14、bandb

15、c,thena

16、c.Proof.(1)Sincea

17、banda

18、c,wehaveb=ma,c=na,m,nZ.Thussb+tc=(sm+tn)a.Hencea

19、(sb+tc)sincesm+tnisaninteger.7DivisionalgorithmTheore

20、m2.1.2.Foranyintegeraandpositiveintegerb,thereexistuniqueintegersqandrsuchthata=bq+r,0r

21、qsuchthatqba<(q+1)b.Letaqb=r,thena=qb+rwith0r