一次同余式组的解法

1、. 学院学 术 论 文一次同余式组的解法A congruence of the solution 姓 名 所在学院 专业班级 学 号 指导教师 日 期 摘要:研究了有关同余式组的解法,特别是孙子定理的应用,当模不两两互质时,就不能用孙子定理来解了,那该怎么办呢?我们将在实例的求解中来揭密.Summary Has studied the related congruence group's solution, specially Residue theorem application, when the mold 22 are not coprime, could not use the

2、 Residue theorem to solve, how should that manage? We will reveal in the example solution.关键字:一次同余式组 模 孙子定理Key words A congruence group Mold Residue theorem正文： 引理1. （孙子定理）设，. 是k个两两互质的正数，m=, m=, i=1,2,k,则同余式组x(mod),x(mod)，x(mod)的解为：x+(modm）,(2)，其中1（mod）,i=1,2,k.证明：由（，）=1，ij 即得（，）=1，故由§1定理即知对每一，有

3、一存在，使得1（mod）. 另一方面m=,因此|，ij，故（mod ）即为（1）的解。若是适合（1）的任意两个整数，则（mod ）, i =1,2, k,因（，）=1，于是（mod m），故（1）的解只有（2） 完【1】引理2 . 设所给的一次同余式组为：X(mod)X(mod )X(mod )（）取m=,则所给同余式组有解的充要是:（）|（）1ijk,且若有解，则对模m的解数为1（未必两两互质）（）找出一组正数满足|，1jk,且两两互质，m=（）若同余式组X（mod ）1jk有解，则它的解与同余式组X（mod ）1jk同解，再用引理1求解。证明：（）充分性：对k用数学归纳法证明当k=2时，显

4、然成立。假设当k=n时，在所给条件满足的情况下，相应的n个同余式组成的同余式有解，当k=n+1时，所给同余式组为：X i=1,2,，n,n+1且满足条件（）|（）i，j=1,2,，n,n+1必要性：我们证明在这些条件下，此同余式组有解。由于|.则X X有解设x=是适合这两个同余式的一个整数，则适合其的一切整数可由X表出。下面考虑如下n个联立同余式X i=1,2,，n-1 X对于这个同余式组，我们有（）|（）i，j=1,2,，n-1又故则又=（，）i=1,2,，n-1这样一来，上述新的同余式组就满足如下条件：（mod）i，j=1,2,，n-1(mod（，）) i=1,2,，n-1于是，由数学归纳

5、法假设这个同余式组有解，而它的解与原同余式组同解。则当n=k+1时，原同余式组有解，则命题成立（，）证明在（）的过程中 【2】例：1.韩信点兵：有兵一队，若列成五行纵队，则末行一人，成六行纵队，则末行五人，成七行纵队，则末行四人；成十一行纵队，则末行十人，求兵数。解：由题意知，x1(mod5), x5(mod6), x4(mod7), x10(mod11)此时=5，=6，=7，=11两两互质，可以用孙子定理求解，则m=5*6*7*11=2310,=6*7*11=462,= 5*7*11=385,=5*6*11=330,5*6*7=210.1(mod)，i=1,2,3,4得=3 =1 =1 =1

6、，故x3*462*1+1*385*5+1*330*4+1*210*1067312111（mod2310）. 【3】2.解一次同余式组x3(mod8)x11(mod20)x1(mod15)解：由于=8，=20，=15，两两不互质，就不能用孙子定理了，要用引理2求解（，）=（8，20）=2 2|8=-（，）=（20，15）= 5 5|10=-（，）=（8，15）=1 1|2=-则同余式组有解。=8=，=20=*5，=15=3*5，m=,=*5*3=120取=8，=5，=3显然|，j=1,2,3.且两两互质，则m=原同余式与同余式x3(mod8)x11(mod5)x1(mod13)同解，由于=8，=5，=3两两互质，可以用孙子定理求解m=*5*3=120，=5*3=15,= 8*3=24,=58*5=40,1(mod)，i=1,2,3,4则=1 =1 =1 x（1）*15*3+（1）*24*11+1*40*12991（mod120）.参考文献：【1】严士健，初等数论第三版，2003年