同余方程的解法毕业论文.doc

本 科 毕 业 论 文题 目： 同余方程的解法 学生姓名： 学 号： 专 业： 数学与应用数学 班 级: 指导教师： 二 一 年 四 月摘要：本文论述了同余方程的基本概念及同余方程的一些基本性质与解法，主要对一次同余方程的解法进行了探讨，特别是对一次同余方程的欧拉定理算法，欧几里德算法等七种解法进行了比较与分析，并介绍了同余方程组、孙子定理、素数模的同余方程，模 的同余方程的解法。关键词： 同余 同余方程 孙子定理 Abstract：This paper mainly discusses the basic concepts of congruence equations and congruence equation some of the basic nature of solution,and highlights the Remainder Theorem,solution of the congruence equation,mod congruence equation solution,congruence equation of primes mode solution,etc.Key words: Congruence Congruence equation Remainder Theorem目录引言11.同余与同余方程的基本性质21.1 同余的概念与基本性质21.2同余方程的概念与性质32.一次同余方程的解法42.1 的情况42.2 的情况73.同余方程组的解法83.1简单同余方程组的解法83.2 孙子定理94.高次同余方程的的解法114.1素数模的同余方程114.2模pa的同余方程12总结：17参考文献18致谢：19引言对于同余方程的解法国内外的数学家们均对其做出了非常全面与细致的研究。在我国古代的数学名著孙子算经中就较早的给出了同余方程的算法即著名的“孙子定理”。我国宋代的大数学家秦九詔，也在他的杰作数书九章中也对同余方程的解法进行了系统的研究。教材中对于同余方程的解法虽然给出了一些方法，但对其研究还不够全面不彻底。所以对于同余方程的解法进行归纳总结，从而作进一步的研究就显得特别重要。1.同余与同余方程的基本性质1.1 同余的概念与基本性质定义1 给定一个正整数，如果用去除两个整数所得的余数相同，那么称对模同余，记作；否则，称同余.记作定理1 设是一个正整数，是两个整数，则的充要条件是存在一个整数使得定理2 模同余是等价关系，即 （i）（自反性）对任意整数,； （ii）（对称性）若, 则； （iii）（传递性）若, 定理 3 整数同余的充分必要条件是除的余数相同.定理4 设一个整数， 是四个整数.如果 , 从而， 定理 5 若, 则 定理6设一个正整数，.如果则 定理7 设一个正整数，, 则 定理 8 设一个正整数，,如果整数则定理9 设是一个正整数，, 如果.定理10 设是一个正整数， , , 则定理11 设是一个正整数，.1.2同余方程的概念与性质定义2 设是整系数多项式，称 (1)是关于未知数的模的同余方程，简称为模的同余方程。若，则称为次同余方程。定义3 设是整数，当时式(1)成立，则称是同余方程的解。凡对于模同余的解，被视为同一个解。同余方程(1)的解数是指它的关于模互不同余的所有解的个数，也即在模的一个完全剩余系中的解的个数。由定义3，同余方程(1)的解数不超过定理12 下面的结论成立：() 设是整系数多项式，则同余方程(1)与等价；() 设是整数，则同余方程(1)与等价；() 设是素数，都是整系数多项式，又设是同余方程(1)的解，则必是同余方程的解。 2.一次同余方程的解法定理13 同余方程() 若有唯一解() 若， 没有解() 若， 有个解2.1 的情况2.1.1观察法在模的完全剩余系中考虑同余式的解，此方法适用在当模较小时或方程具有特殊形式的一次同余方程里例1：的解为2.1.2欧拉定理算法由欧拉定理有，而可得既得：为所求的解。此解法适合较小或较易求解例2：解解，2.1.3化为不定方程的解法有解存在整数使得。即不定方程有解。此解法对模的要求较低。例3：解解：原方程对应的不定方程为其通解为（对任意的整数），所以2.1.4减小模数的解法对于 此时，然后去掉中的倍数不断将模变小此时若有解，则为的解。经过几次转换后一般可以用观察法求解，在递推出原方程的解。此方法适合模数较大的同余方程。例4：解同余式解：原同余式即是：，解同余式：得：，所以原同余式的解是：2.1.5欧几里得算法可借用辗转相除法求整数的最大公因数的方法，结合同余式的性质，可转化为一个形如的同解方程。当利用恒等变形将变小，直至将的系数化为1.若, 且模数较大时, 可用取余的办法, 将变小, 然后求出解。例5: 解同余式.解: , 原同余式有1 个解。,而, 。,而,即为原同余式的解。若, 且中至少有一个数大于m , 可根据同余知识, 将化小, 再用方法去解。例6: 解解: ,原同余式化为:,而,。又,。为原同余式的解。2.1.6分式法先把写成的形式（这里是一种形式的写法）然后用与互素的数陆续的乘又端的分子和分母，目的在于把分母的绝对值变小，直到变成1为止。此方法使用模不太大如三位数或三位数以内的。例7：解同余是解2.1.7威尔逊定理解法为素数，由威尔逊定理有：此方法适用模为素数且模不能太大。例8：解解2.2 的情况， 有个解2.2.1化为法对于先用去除同余式，在按的情况去解。例9：求的解解 原方程有4个解。用4去除同余式得：而，原同余式的解为2.2.2消去的系数解同余式逐次消去的系数例10： 解同余式。解：因为，同余式有个解。原同余式可化简为，与的公因数与互质，可消去公因数，同余式进一步化简为：。与的公因数与互质，可消去公因数，同余式可化简为：，是的倍数故：。原同余式的个解为：。利用辗转相除法消去 的系数对于系数较大、较复杂的同余式, 可以采取辗转相除法消去 的系数。例11：解同余式解：因为同余式有个解。化简：，用辗转相除法，将上述过程反演得到：所以：因为同余式的5个解为：3.同余方程组的解法3.1简单同余方程组的解法对于同余方程组 （1）当时的简单解法。例12. 解同余方程组。 (2)解 : 将(2)的前一式乘以2后一式乘以3再相减得到再代入(2)的前一式得到即同余方程组(2)的解是。3.2 孙子定理定理14(孙子定理) 设是正整数， 记， ，则存在整数，使得， 并且 （3）是同余方程组(1)对模的唯一解，即若有使方程组(1)成立，则。 定理15 同余方程组(1)有解的充要条件是 定理16 设，其中是两两互素的正整数，是整系数多项式，以与分别表示同余方程 与 的解的个数，则例13. 求整数，它被除的余数分别是解:是同余方程组的解。根据孙子定理，取则因此所求的整数例14. 解同余方程。 (4)解: 因为，所以，由定理16可知，同余方程(4)等价于同余方程组 (5) (6) (7)分别解同余方程(5)，(6)，(7)得到解，同余方程(4)的解可转化为下面的方程：，其中或，或。利用孙子定理，取则。将所有可能的取值代入上式，得到方程(4)的全部解是，。4.高次同余方程的的解法4.1素数模的同余方程设是整系数多项式，是素数， 。定理17 设若同余方程 (1)有个不同的解则对于任意的整数有，其中是一个次数为的整系数多项式，并且它的项的系数是定理18 同余方程(1)的解数定理19 同余方程(1)与一个次数不超过的质数模同余式等价。定理20 设，则同余方程有个解的充要条件是存在整数多项式和，的次数使得定理21 (定理)若是素数，则 例15. 判定同余方程是否有三个解。解: 因为，所以，原方程与即等价。由于所以，由定理20和定理18可知，原方程的解数小于。例16. 解同余方程。解: 由定理，又因为因此，由定理19原同余方程等价于：即 。 （2）将分别代入方程（2）进行验证，可知这个同余方程解是4.2模pa的同余方程求解模的同余方程可以转化为对模的同余方程的求解。若是同余方程 (1)的解，则它必是方程 (2)的解，因此，必有与相应的方程(2)的某个解，使，此处，是某个适当的整数。定理22设是素数，是整数，是整系数多项式，又设是同余方程(2)的一个解。以表示的导函数。() 若，则存在整数，使得 (3)是同余方程(1)的解。() 若并且，则对于，式(3)中的是方程(1)的解。由定理，可以把解同余方程(1)，转化为解同余方程。 (4)由方程(4)的解，利用定理，可以求出方程的解，再利用定理，又可以求出方程的解，LL，直到求出方程(1)的解。推论1 使用定理的记号，() 若是同余方程(4)的解，并且，则存在，使得是同余方程(1)的解。() 若与同余方程(4)没有公共解，则对于任意的整数，同余方程(1)与(4)的解数相同。例17. 解同余方程。解: 根据定理16 原同余方程等价于同余方程组， (5)。 (6)先解同余方程(5)。同余方程的解是。令并代入方程(5)，得到， (7)由定理22()这是一个对于任何整数t都成立的同余式，所以，方程(7)的解是，于是方程(5)的解是。 (8)再解同余方程(6)。用去验证，得到(6)的解是。因此，原同余方程的解是下面六个同余方程组的解：利用孙子定理解这六个方程组，记，则。将，。例18. 解同余方程。 (9)解: 同余方程 (10)有两个解。令， (11)代入同余方程， (12)得到，。 (13)于是，将式(11)与式(13)联合，得到方程(12)的解。 (14)将式(14)中的代入同余方程(9)，得到 ，。将上式与(14)联合，得到同余方程(9)的一个解。 从同余方程(10)的另一个解出发利用上述方法，可以求出同余方程(9)的另一个解为。例19. 解同余方程。 (15)解: 若，则方程(15)的解是。若，则方程(15)的解是。若，则同余方程(15)，即，的解必是奇数，设，则同余方程(1)成为，。 (16)同余方程(16)的解是，即，所以，方程(15)的解是，即。总结：本文应用前人的研究成果，对同余方程的常用解法进行了系统的归纳总结，并对其解法进行了进一步的研究优化。其主要对一次同余方程的解法进行了详细的介绍，其次对用孙子定理来解同余方程组做了初步的总结，最后叙述了素数模及模的同余方程的解法，但本文只是讲了一些同余方程的常见解法，希望读者在这方面有更好更多的见解。参考文献 柯召，孙琦.数论讲义上册M. 高等教育出版社,北京,2001年 闵嗣鹤,严士健.初等数论第三版M.高等教育出版社,北京,2003年 潘乘洞、潘乘彪.初等数论M.北京大学出版社第二版,北京，2003年 杜德利.基础数论M.周仲良,译.上海科技出版社,上海1982年 刘合义.谈数论中的同余及其应用J.衡水师专学报,2002年 原新生.一次同余方程的几种解法J.牡丹江教育学院学报,2009年致谢： 时光匆匆，如白驹过隙。在毕业论文定稿之际，四年的大学本科生活也即将画上句号。遥想初入大学之时，还历历在目，恍如隔日，不免感叹光阴易逝、韶华难追。然而，艰辛而快乐的求学之路，也给我留下了很多难以忘怀的欣慰和幸福。在此，向四年来陪伴我一起走过，给予我帮助和关心的良师益友以及亲人们，致以最为真挚的谢意！ 我衷心的感谢我的导师 ，她在我毕业设计的题目选择上给与了非常大的帮助，并且在整个毕业设计过程中一直指导、鼓励着我，使我能够顺利完成毕业设计的工作。- 19 -