费马小定理的证明与应用.doc

《费马小定理的证明与应用.doc》由会员分享，可在线阅读，更多相关《费马小定理的证明与应用.doc（41页珍藏版）》请在三一办公上搜索。

1、本科学生毕业论文费马小定理的证明与应用 黑 龙 江 工 程 学 院二一二年六月The Graduation Design for Bachelors Degree Proofs of Fermats little theorem and its applicationsHeilongjiang Institute of Technology2012-06Harbin黑龙江工程学院本科生毕业论文摘 要本文第一章阐述了数论中很重要的定理费马小定理，以及要证明费马小定理的准备知识，重点阐述了剩余系定理、同余定理，还包括同余的概念和性质。在本文的第二章中，我们应用同余的性质，欧拉定理，构建剩余系法，数

2、学归纳法，近代数学方法（群论知识）五个方法对费马小定理进行了证明。第三章阐述了费马小定理在初等数论和竞赛数学等9个方面的应用，如证明欧拉定理、wilson定理、判断不定方程的解的存在性等。第四章讨论了费马小定理的逆命题，根据绝对伪质数的存在性说明了费马小定理的逆命题是一个伪命题。本文最后还描述了费马小定理在洗牌当中的妙用。关键词：费马小定理； 同余； 整除； 不定方程ABSTRACTThe first chapter introduces the theory of an important theorem of Fermats little theorem, as well as to pr

3、ove Fermats little theorem ready knowledge, elaborated with emphasis the remaining line theorem, congruence theorem, also includes the concept and properties of congruence. In the second chapter, we apply the congruence properties, Eulers theorem, building a remaining line method, mathematical induc

4、tion, modern mathematical methods ( group theory knowledge ) five methods on Fermats little theorem is proved. The third chapter of Fermats little theorem in elementary number theory and mathematics competition in 9 aspects such as application, proof of Eulers theorem, Wilson theorem, judge the inde

5、finite equation solution existence. The fourth chapter of Fermats little theorem converse proposition, according to the absolute pseudo prime existence that Fermats little theorem converse proposition is a false proposition. This paper also describes the Fermats little theorem in the application of

6、shuffle.Key words: Fermats little theorem; Congruence; Divide exactly;Indefinite equation目 录摘 要IABSTRACTII第1章 绪 论11.1 费马小定理的概念11.2 证明费马小定理的准备知识11.3 本章小结4 第2章费马小定理的证明42.1 初等方法 利用同余的性质证明42.2 欧拉定理的推广52.3 构建剩余系法52.4 数学归纳法72.5 近代数学方法（群论知识）82.6 本章小结8第3章 费马小定理的应用93.1 应用费马小定理计算余数问题93.2 应用费马小定理证明一些整除问题93.3 应

7、用费马小定理证明欧拉定理103.4 应用费马小定理证明Wilson定理113.5 应用费马小定理简化求解高次同余方程123.6 应用费马小定理得出同余方程有解的必要条件143.7 应用费马小定理巧解某些数学竞赛题143.8 应用费马小定理判断不定方程的解的存在性153.9 应用费马小定理解某些指数不定方程163.10 本章小结16第4章 费马小定理的逆命题204.1 绝对的伪质数214.2 在洗牌中的妙用214.3 本章小结21参考文献24致 谢25附 录26IV第1章 绪 论1.1 费马小定理的概念费马(P.Fermat,1601.81665.1),法国数学家。出生于图卢兹,早期学习法律学并

8、担任过律师。他精通数国语言，对于数学及物理也有浓厚的兴趣，是一位多采多艺的人。虽然他在近三十岁才开始认真专研数学，但是他对数学的贡献使他赢得业余王子（the prince of amateurs）之美称。这个头衔正足以表彰他在数学领域的一级成就。费马在数论方面有两个举世闻名的研究成果：1. 费马大定理： ，当时没有整数解；2. 费马小定理：当为素数,对任意的整数都有： 如果不是的倍数，即，这个定理也可写成：费马小定理是数论中很重要的定理，这个定理第一次出现于1640年的一封信中，此定理的证明后来由欧拉（Euler）发表。很多数论教科书中费马小定理的证明都是由欧拉定理的证明而给出的，并看作是欧拉

9、定理的推广。事实上，费马小定理是先于欧拉定理得到证明的。费马小定理是初等数论四大定理（威尔逊定理，欧拉定理（欧拉定理，即欧拉函数理论），中国剩余定理和费马小定理）之一，具有极其广泛和重要的应用。事实上，它是一个欧拉定理的特殊情况（即“欧拉函数”）。1.2 证明费马小定理的准备知识要想证明费马小定理，首先要先我们要了解以下四个引理。 （见文献1）引理1剩余系定理2如果为3个任意整数，为正整数，且,互质，则当时，有。 证明：由可得化简得：又因为互质，可以约去，所以：可得：引理2剩余系定理5如果为整数且1,为个整数，若在这个数中任取2个整数对不同余，则这个整数对构成完全剩余系。 证明：构造的完全剩余

10、系（0,1,2，-1），所有的整数必然与这些整数中的1个关于模同余。取： 。 令： , , , （顺序可以不同），因为只有在这种情况下才能保证集合：中的任意2个数不同余，否则必然有2个数同余。由式（1）自然得到集合对构成完全剩余系。 引理3剩余系定理7假设是个整数，且，是一个整数且互质。如果是模的一个完全剩余系，则也构成模的一个完全剩余系。 证明： 若存在2个整数和同余即，根据引理1则有： .根据完全剩余系的定义和引理4（完全剩余系中任意2个数之间不同余，易证明）可知这是不可能的，因此不存在2个整数和同余。由引理5可知：构成模的一个完全剩余系。 引理4同余定理6 如果是四个整数，且 , ，则有

11、： ,证明： 由题设得： , ,由模运算的传递性可得： .简单的说，在数学上，若两个整数除以同一个整数，如果取得相同余数，那么我们就说这两个整数同余。记作，读作同余于模m，或读作与关于模同余。例如 ： 本文要采用多种方法来证明费马小定理，所以会用到同余的很多性质，在此我总结出同余的多个性质，来为费马小定理的证明做些准备工作。（见文献2、3）性质如下：性质1：，（反身性）这个性质很显然.因为：。性质2：若，那么，（对称性）。性质3：若，那么，（传递性）。性质4：若，那么，（可加减）。性质5：若，那么（可乘性）。性质6：若，那么，（其中n为自然数）。性质7：若，那么，（记号（c，m） 表示与的最大

12、公约数，也就是互质）。性质8：若，那么的次方和的次方也对于同余。性质9：若、 、， 那么：和对于同余。1.3 本章小结在第一章绪论中，我们主要介绍了费马大定理，费马小定理的概念，以及证明费马小定理所需要的前提知识：剩余系定理、同余定理。最后个人总结了同余的9个性质。第2章 费马小定理的证明费马小定理：当为素数,对任意的整数都有 （2.1）如果不是的倍数，即 ，这个定理也可写成： 许多年以来，众多数学爱好者从不同的角度给出了费马小定理的证明。本文通过对众多证明方法所应用的基础理论的研究，将费马小定理的证明归纳整理为以下五种方法：2.1 初等方法 利用同余的性质证明2.1初等方法 (见文献4)证法

13、一：利用同余的性质对任意的非负整数及素数，恒有 令得以上各式左右分别相加得 2.2 欧拉定理的推广欧拉定理 设，则有 （2.2）其中是正整数，是小于且与互素的正整数的个数,称欧拉函数。证明：由（2.2）式取为素数且及 得： 而当时显然有（2.1）式成立。 故当为素数时，对任意的整数都有： 费马小定理得证。2.3 构建剩余系法 证明：设与互素，构成的一组非零剩余系，而是的一组非零剩余系，所以有 ： 化简后得两边同除以 即得： 即 ：而当时，费马小定理显然成立。2.4 数学归纳法引理1： 对于组合数，当为素数且时均能被整除。由组合数的性质知，当，为素数时，显然有。因为对于任一整数，都有易得引理2。

14、引理2： 对于任一整数，都有：。费马小定理的另一种表述为：令为一素数，对任意的整数，必为的倍数。证明：应用数学归纳法，对进行归纳 （I） 当时，费马小定理显然成立； （II）假设当时，定理成立，即能被整除 则当时 ： （2.3） 由前面两个引理知（3）式等号右边两部分均能被整除，即必为的倍数，故对于任一非负整数，费马小定理成立；同理可证，对于任一负整数，费马小定理也成立；综上所述，对任一整数，费马小定理成立。近来有人在对杨辉三角中的每个元素进行质因子分解的时候，发现第行（为素数）除了首尾两个元素为“1”外，其余元素都可以被整除。考虑到杨辉三角的行和是，于是作者猜测可能被整除，其实这就是费马小定

15、理当时的特例。应用这个性质来证明费马小定理也是用的数学归纳法。（见文献5）2.5 近代数学方法（群论知识）有一种较独特的证明方法是将剩余系放到群的理论当中，将群的相关理论与费马小定理建立联系，设为一个阶群，由拉格朗日定理知 ，从群的角度巧妙的证明了费马小定理。（见文献4）引理：（拉格朗日定理）假设是一个有限群，是的子群，则的阶整除的阶。证明：设是一个群，运算为乘法，是的一个非空子集.对于任意,我们定义这个集合：由定义的映射是一个双射，所以对于所有的，.假设是的子群，那么被称作的一个陪集.设和是子群的陪集.，则存在，使得，或者，由于是一个子群，这里.对于所有的，所以同理，,所以因此子群的陪集不交

16、或相等.由于的每个元素属于的陪集（例如，对于所有的都有），从而可得出划分G的陪集.我们用表示陪集.假设是一个有限集，则，是有限的，及特别地，我们有整除设是一个群，运算为乘法.设，=Z，则.由于对所有的，Z,，从而可得出是的子群.这个子群被称作由生成的循环子群，记作，循环子群都是交换的.如果存在一个元素，使得，则群是循环群.此时，元素称作的生成元.例如，群是由生成的阶为6的循环群.同余类是这个群的另一个生成元.如果对于所有整数，都有，则由生成的这个循环群是无限的.如果存在和，使得，则.设是最小的正数，且使得，则这个群的元素，是不同的.设，由除法知，存在整数和，使得， .由于，从而有Z，由生成的这

17、个循环群的阶为，而且，当且仅当，才有. 设是一个群，.我们可以将的阶定义为由生成的循环子群的基数.利用群论知识证法4 利用群论知识因为一切与模p互素的剩余类对于剩余类的乘法做成一个群G，该群的阶为，且群G的单位元为1.设，则，若的阶为,则。因此，于是.2.6 本章小结在第二章之中，我们依次利用了同余的性质、欧拉定理、构建剩余系法、数学归纳法、近代数学方法（群论知识）来对费马小定理进行了证明。第3章 费马小定理的应用费马小定理的重要是因为他的应用的广泛性，它不仅可证明一些同余式方面的数论问题和竞赛问题，而且也能证明其他的数论中的重要的定理。下面就其应用进行分类介绍：3.1 应用费马小定理计算余数

18、问题例： 解： ， 。3.2 应用费马小定理证明一些整除问题例： 设是任一正整数，证明：也是正整数。证明： 因为： 所以只需证 ： 由费马小定理有： ， ， 令 ：，又因为： 即： 同理： 即： 同理： 即： 则有： ， ， ，又由于两两互素，所以，即若不应用费马小定理，而用整除的性质，就要分几种情况讨论，显然比本例的解法要麻烦得多。（见文献6、7）3.3 应用费马小定理证明欧拉定理例： 证明：设 对素数，由费马小定理有 即，于是有即同理可得则有 又由于两两互素，所以即欧拉定理得证。3.4 应用费马小定理证明Wilson定理证明：由费马小定理知，次同余方程 ： ，恰有个解 ，于是：。取 ，即得

19、： .3.5 应用费马小定理简化求解高次同余方程对模为素数的高次同余方程（设）直接求解是非常困难的，利用整系数多项式除法和费马小定理都可以把它转化为与其等价的同余式，进而达到化简和求解的目的。但相比较而言，利用费马小定理要比利用多项式除法简便得多。 例： 简化同余方程：。解：由费马小定理及同余的性质可得 由上式知： 综上所述： ， ， 因此原同余方程等价于 进而等价于讨论：因为是模5同余，所以分5种情况： 1）令： 则： 得： 所以本结果成立。2）令： 则： 得： 所以本结果成立。 3）令： 则： 得： 所以本结果成立。4）令： 则： 得： 所以本结果成立。 5）令： 则： 得： 所以本结果成

20、立。经过讨论可得： 。如果利用多项式除法可得到同样的结果，但显然要麻烦得多！3.6 应用费马小定理得出同余方程有解的必要条件 证明：3.7 应用费马小定理巧解某些数学竞赛题 同余是数学竞赛的重要组成部分，而费马小定理又是同余理论中重要的定理，因此应用费马小定理可以巧妙的来解决一些竞赛题。（见文献8、9）例： 设为大于的素数，求证在数列中有无穷多项是的倍数。证明：且是素数，所以，由费马小定理可得， 即：，为正整数。而 由于，所以 ， 从而问题得证。3.8 应用费马小定理判断不定方程的解的存在性证明：不定方程 （3.1）无解。证明：对（3.1）式两边取模3知 （3.2） 由费马小定理（3.2）式可

21、化为 （3.3） 对于（3.3）式可分为3种情形来讨论：1)；2)；3) 在情形1)中，由于： ， 对（3.1）式取模得： ， 这与相矛盾； 在情形2)中，对（3.1）式取模得： ， 这显然是不成立的； 在情形3)中，与情形2)类似。 综上可得（3.1）无解。3.9 应用费马小定理解某些指数不定方程在解指数不定方程前，要先介绍一下雅可比符号：（见文献10）雅可比符号是一个对于给定的大于1的单质数定义在一切整数上的函数，它在上的函数值是： 其中 ，是质数。是对的勒让德符号。勒让德符号概念：勒让德符号是由法国数学家勒让德所发明的一种符号，这个符号是为了简化二次剩余的计算而产生，而因为这个符号的发明

22、，使得二次剩余有更多的性质能被彰显出来。 勒让德符号，对整数和奇素数有下列定义：假设，如果有解，则叫做模的平方剩余。假设，如果无解，则叫做模的平方非剩余。雅可比符号是勒让德符号的推广，但是根据雅可比符号的值不能判断同余式是否有解。勒让德符号的几个性质： 性质（1）： 。 性质（2）：若 ，则 。 性质（3）：若 ，则 。 性质（4）： 。 性质（5）：若不能被整除，则 。 性质（6）： 。 性质（7）：若都是单质数， ，则 。 性质（8）： 。例： 证明方程 (见文献11、12) （3.4）无解。 证明：显然，取模4知为奇数， 设，由费马小定理可得： 故，即，也即由欧拉定理得经计算仅当时上式成

23、立，故；再取模且，仿上可得由101为素数及费马小定理知经计算得于是有从而 （3.5）这里表示雅可比符号。 1. 由勒让德符号的性质（4）得： ， ，2. 由勒让德符号的性质（6）得： 。 （3.6） 3. 由勒让德符号的性质（7） 得： ， ， ， 再由勒让德符号的性质（3）得： 因为： ， ， 所以： ， ， ， 最后由勒让德符号的性质（6）得： ， ， 即： 。 （3.7） 。 （3.8） 4. 由勒让德符号的性质（8）得： ， 即： ， （3.9） 综上所述：由（3.6）、（3.7）、（3.8）、（3.9）得：此与（3.5）式矛盾。所以方程（3.4）无解。3.10 本章小结在第三章中，我

24、们主要阐述了费马小定理在初等数论和竞赛数学等9个方面的应用，这些说明了费马小定理有着广泛的应用。第4章 费马小定理的逆命题当为质数，由费马小定理我们知道必定是的倍数；反过来说成不成立那？也就是说，如果有某个正整数可以整除，我们能不能断定一定是质数那?如果可以的话，这将是个不错的判别任意整数是否是伪质数的方法；历史上确实曾经有一段时期数学家们猜测这个方法是可行的，不过法国数学家Pierre Sarrus于西元1819年指出是一个反例；341是11与31的乘积，因此不是质数，但是由于：可知341能整除 。对于任意正整数,如果有某个大于1的正整数本身不是质数却能整除,我们称对底数而言是一个伪质数，因

25、此对底数2而言，341是一个伪质数。几个衍生出来的问题：341是惟一的伪质数吗？除了奇数的伪质数外，是否还存在着偶数的伪质数？对任意正整数,伪质数的个数是有限还是无限？对于底数2而言，如果是一个奇伪质数，我们不难证明将是另一个更大的奇伪质数；既然我们已知奇伪质数341的存在，对底数2来说奇伪质数的个数因此是无穷的。寻找偶伪质数（对底数2而言）的工作比寻找奇伪质数要困难许多，其中最小的数直到公元1950年才由美国数学家D.H.Lehmer找到，其值为，由于要说明161038可以整除，我们只需说明73与1103（两数皆为质数）都能整除即可，由于161037可经质因子分解为 。因此：可知73能整除2

26、161037-1，由于因此1103的确也能整除，数学家N.G.W.H.Beeger于1951年证明了对底数2而言，偶伪质数的个数也是无穷的。数学上还能证明：对任意正整数,以为底数的伪质数的个数都是无穷的。4.1 绝对的伪质数以2为底数的伪质数的个数是无穷的，以3为底数的伪质数的个数也是无穷的；是否存在整数使得既是以2为底的伪质数，又是以3为底的伪质数呢？答案是肯定的；令人惊讶的是，我们甚至还能找到合数使得不管是多少，都能整除,也就是说，存在合数使得全都是的倍数。这样的不仅存在而且还有不只一个，其中最小的是 。由于而由费马小定理可知必定是11的倍数，因此必定也是11的倍数，经由此类似方法可推知也

27、必定是3的倍数和17的倍数，因此不论是多少，必定是561的倍数。如果不论多少,合数都能整除,数学上称为一个绝对伪质数，因美国数学家R.D而得名，他在公元1909年首先注意到有这种数的存在，最小的十个依序为：561,1105,1729.，2465,2821,6601,8911,10585,15841,29341。绝对伪质数的总数到底是有限或是无限的问题曾经困扰了数学家许多年，直到1994年才被证明出来其个数是无穷的。（见文献13）绝对伪质数在数的线的分布比质数稀疏多了，例如在所有小于一百万的正整数中，总共有个78498个质数，总共有245个以2为底的伪质数，但是总共只有43个伪质数。4.2 在洗

28、牌中的妙用考虑以下动作：将一副扑克牌（52张）由中间分成各含26张牌的两小迭，然后洗牌使得这两迭牌一张一张交错，重新组合成52张牌，下图显示了洗牌前后位置的变化：271271282822293 293522626 图（4.1）我们称以上动作为一次洗牌。请问：经过洗牌几次后可使每张牌都回到它最原始的位置？由图（4.1）洗牌前后的位置变化，我们看到原来在位置编号1,2,3,，26的牌经过一次洗牌后将被放到编号2,4,6，52的位置，而原来编号27,28,29，52的牌则被放到了编号1,3,5，51的位置，因此如果某张牌原来的位置为,经过一次洗牌后的位置为,那么与的关系为;因此正张牌经过次洗牌后的位

29、置必定与对模53同余，而我们的目标是希望能找到某个使得对所有，。既然与53互质（因为53为质数），我们可将上式左右两边的约掉而得：由费马小定理我们知道一定满足上式；事实上，52是满足上式最小的(我们在此不予证明)。因此经过52次洗牌后所有的牌都必定回到了原始的位置。一般而言，如果一副牌有张（为偶数），而正整数满足：那么经过上述方式洗牌n次后所有的牌都回到了原始的位置。举例： 如果,那么我们只需洗牌6次即可，因为：费马小定理的逆命题（converse）虽然不成立，不过伪质数与Carmichael numbers的数量在所有正整数中毕竟只占少数，因此如果不是质数： 我们在小学都学过如何判断一个正整

30、数是否为质数，只要测试介于1与之间的整数是否有的因子即可(事实上只须测试个数即足够)；）；但是当很大时（例如当是200位数），要判断是否为质数的工作将变得相当困难.我们这里所谓的难当然不是说完全没有方法解决，而是很难在短时间内解决；然而质数的判定却是某些领域里常需面临的问题，例如密码学里就有许多算法在应用上需要由计算机随机产生很大的质数，因此实际应用上很需要有较快的方法来判断一个大整数是否为质数。当我们要判断是否为质数，如果我们选择几个不同的值（例如 = 2，3，5，7），分别计算除以的余数，结果发现所有的余数都是1，那么为质数的机率其实相当高，而如果有任何一个余数不是1我们立即可确定不是质数

31、.这个方式虽然不能保证通过测试的一定是质数，但是在大部分情形下却可以有效地将合数剔除，可以在判断质数的过程中提供初步而快速的筛选，因此为许多实际程序所采用。（见文献14）4.3 本章小结在第四章中，我们谈论了费马小定理的逆命题，但是通过伪质数的存在，我们知道费马小定理的逆命题是伪命题，最后介绍了费马小定理在洗牌的妙用。结束语费马小定理最早出现在公元1640年Fermat写给友人的一封信上，他在信中声称他知道如何证明这个定理，只是因为纸张的空间太小了以致未能写下其证明。正式发表的证明要等到大约100年后才由数学家Euler于1736年提出，Euler所用的方法是利用二项式定理的方式，不过由数学家

32、Leibniz留下的未发表过得手稿显示他应该早在1683年之前就已经用相同的方法证明出来了。如果某个合数满足：对任意整数,只要与互质，就一定能整除，那么其实就是一个绝对伪质数。既然有费马小定理，那么自然就有费马大定理，费马大定理也就是一般俗称的费马最后定理（Fermats last theorem）。大于小只是在名称上做区隔，就重要性而言，费马小定理其实并不小，它所表达的关系不仅漂亮，在数学上更有相当广泛的应用。初等数论被认为是理论与实践结合得最完美基础课程，而费马小定理又是其中比较重要的定理之一，由于其应用的广泛性，受到了越来越多的重视。通过对费马小定理应用的研究，可以使我们认清费马小定理的

33、重要性；培养我们数学思维的广阔性。参考文献1潘承洞.初等数论（第二版）. 北京：北京大学出版社，2003.2林晓燕.谈同余理论在初等数学中的几点应用J.怀化学院学报，1995年05期.3徐诚浩.同余式及其应用：高等教育出版社，2009年12月1日.4潘承洞.初等数论J . 北京：北京大学出版社，1992. 5孙幸荣.Fermat小定理的巧证及应用.商洛师范专科学校学报，2004.02期.6李晕.2009马其顿数学奥林匹克，2010.7王鹭萍.整值多项式的若干问题研究及其应用J.漳州职业技术学院学报，2010年第4期.8Jarosaw Kotowicz. Functions and finite

34、 sequences of real numbers. Journal of Formalized Mathematics，1993.9曾荣.基础数论典型题解300例J.长沙：湖南科学技术出版社，1982.10杨玉红.Fermat小定理的若干证明及应用云南师范大学学报(自然科学版)，2001.6期.11C.F.Gauss .Disquisitiones Arithmeticae (English)：Springer，2007.12许介彦.数不尽的质数.科学教育月刊，2002年254期.13Melvyn B. Nathanson . Elementary Methods in number th

35、eory ：Computer Science Press，2007.14郭凤琴.初等数论河南师范大学数学系.代数基本定理：152-154.15吴延东.符号动力系统与费马小定理J，2009年25期. 致 谢在论文完成之际，首先我要感谢王世英老师的亲切指导，从论文选题、撰写、反复修改到定稿过程中，王老师给我提出了很多宝贵的意见和富于启发的思路，严格要求的同时也倾注了许多的关怀，始终给予了悉心指导王世英老师严谨的治学态度和高度负责的敬业精神，对我现在及未来的学习和工作，起到了很大的榜样作用其次我还要感谢大学四年中所有老师、同学对我的关心、鼓励、支持和热情帮助在此一并表示诚挚的谢意！附 录Eulers

36、 Theorem and Fermats TheoremPage:2.5 Eulers Theorem and Fermats TheoremEulers theorem and its corollary ,Fermats theorem ,are fundamental results in number theory ,with many applications in mathematics and computer science .In the following sections we shall see how the Euler and Fermat theorems can be used to determine whether an integer is prime or composite ,and how they are applied in cryptography.Theorem2.12（Euler）Let be a positive integer, and let be an integer relatively prime to .Then.Proof. Letbe a reduced set of residues modulo .Since ，we have for .Consequently, fo