研FMIS-Ch4-TheoryOfCongruences

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

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

2、berTheoryChapter2TheoryofDivisibilityChapter3DistributionofPrimeNumbersChapter4TheoryofCongruencesChapter5ArithmeticofEllipticCurves3Chapter4TheoryofCongruences4.1BasicConceptsandPropertiesofCongruences4.2ModularArithmetic4.3LinearCongruences4.4TheChineseRemainderTheorem4.5High-OrderCongruences4

3、.6LegendreandJacobiSymbols4.7OrdersandPrimitiveRoots4.8Indices44.1BasicConceptsandPropertiesofCongruencesDefinition4.1.1Letabeanintegerandnapositiveintegergreaterthan1.Wedefine“amodn(a模n)”tobetheremainderrwhenaisdividedbyn,thatisr=amodn=aa/nn.Wemayalsosaythat“risequaltoareducedmodulon(r等于a模n的

4、约化)”.Remark4.1.1Itfollowsfromtheabovedefinitionthatamodnistheintegerrsuchthata=a/nn+rand0r

5、eptsofCongruencesDefinition4.1.2Letaandbareintegersandnapositiveinteger.Wesaythat“aiscongruenttobmodulon(a与b模n同余)”,denotedbyab(modn),ifnisadivisorofab,orequivalently,ifn

6、(ab).Similarly,wewritea≢b(modn),ifaisnotcongruent(orincongruent)tobmodulon,orequivalently,ifn∤(ab).Clearly,forab(modn)(re

7、sp.a≢b(modn)),wecanwritea=kn+b(resp.akn+b)forsomeintegerk.Theintegerniscalledthemodulus.7BasicConceptsofCongruencesRemark4.1.2.Clearly,ab(modn)n

8、(ab)a=kn+b,kZ.anda≢b(modn)n∤(ab)akn+b,kZ.Remark4.1.3.TheancientChinesemathematicianCh’inChiu-Shao(QinJiushao,秦九韶,南宋,约1202-1261)alreadyhadthe

9、ideaandtheoryofcongruencesinhisfamousbookMathematicalTreatiseinNineChapters(数学注释九章)appearedin1247.8BasicConceptsofCongruencesDefinition4.1.3Ifab(modn),thenbiscalledaresidue(剩余)ofamodulon.If0bn1,biscalledtheleastnonnegati