一次同余式组的解法

《一次同余式组的解法》由会员分享，可在线阅读，更多相关《一次同余式组的解法（7页珍藏版）》请在装配图网上搜索。

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

2、olve, how should that manage? We will reveal in the example solution.关键字:一次同余式组 模 孙子定理Key words A congruence group Mold Residue theorem正文：引理 1. （孙子定理） 设 m ，m . m 是 k 个两两互质的正数，1 2 km= mm m , m= mM , i=l,2,，k,贝U同余式组 x= b （modm ）,x= b （modm ）,，1 2 k i i 1 1 2 2详bk（mod代）的解为：x= M M b + M M b +M M b （modm

3、）,l l l 22 2k k k其中 M M =1 （modm ） ,i=l,2，k.ii证明：由（m , m ） =1, i# j即得（M , m ） =1,故由 1定理即知对每一M ,i j i i i 有一 M 存在，使得 M M =1 （modm ）.i i i i另一方面m= m M，因此m |M , i#j,故i i j i丈 M M b = M M b = b （mod m ）即为（1）的解。j j j i i i i ij=1若x , x是适合（1）的任意两个整数，则12x = x （mod m ） , i =1,2,k,1 2 i因（m , m ） =1,于是x = x （

4、mod m）,故（1）的解只有（2）完【1】ij12引理2 .设所给的一次同余式组为：X= b (modm )11X= b (mod m )22X= b (mod m )kk(i) 取m=m ,m ,m，m ，则所给同余式组有解的充要是：1 2 3 k(m ,m ) | ( b b ) lWiMjWk,i j i j且若有解，则对模m的解数为1 ( mmm未必两两互质)1 2 k(ii) 找出一组正数m ,m ,m 满足m im , 1WjWk,且m ,m ,m 两两互质,1 2 k j j 1 2 km= m m m 1 2 k(iii) 若同余式组X= b (mod m ) 1WjWkjj

5、有解，则它的解与同余式组X三b (mod m ) 1WjWk同解，再用引理1求解。jj证明：(i)充分性：对k用数学归纳法证明 当 k=2 时，显然成立。 假设当k=n时，在所给条件满足的情况下，相应的n个同余式组成的同余式有 解，当 k=n+1 时，所给同余式组为：X= b (modm ) i=l,2,., n,n+1ii且满足条件 (m ,m ) | (b b ) i，j=1,2，n,n+1i j i j必要性：我们证明在这些条件下，此同余式组有解。由于(m ,m ) |(b ,b ).n n+1n n+1贝ij x= b (modm ) x= b (modm )有解nnn +1n +1设

6、 x=c 是适合这两个同余式的一个整数，则适合其的一切整数可由kX= c (modm , m )nn n+1表出。下面考虑如下n个联立同余式X= b (modm ) i=1,2,，n-1iiX= c (modm , m )nn n +1对于这个同余式组，我们有(m ,m )|( b -b ) i, j=l,2,，n-1i j i j又c三b (mod m )n nnc = b (mod m )nn+1n+1b = b (mod(m , m )ini nb = b (mod(m , m )in +1i n +1故 b = c (mod(m , m )ini nb = c (mod(m , m )

7、in +1i n +1则 b = c (mod(m , m ),(m , m )ini ni n+1又(m ,m ),(m ,m )= ( m , m ,m ) i=1,2,，n-1i ni n+1in n+1这样一来，上述新的同余式组就满足如下条件：b = b (mod(m ,m ) ) i, j=1,2,，n-1i j i jb = c (mod ( m， m ,m ) ) i=1,2,，n-1inin n+1于是，由数学归纳法假设这个同余式组有解，而它的解与原同余式组同解。则当n=k+1时，原同余式组有解，则命题成立(ii,iii)证明在(i)的过程中【2】例： 1.韩信点兵：有兵一队，

8、若列成五行纵队，则末行一人，成六行纵队，则末行五人，成七行纵队，则末行四人；成十一行纵队，则末行十人，求兵数。解：由题意知，x=1(mod5), x=5(mod6), x=4(mod7), x=10(mod11)此时m =5， m =6，m =7， m =11两两互质，可以用孙子定理求解，1234则 m=5*6*7*11=2310,M1 =6*7*11=462,M = 5*7*11=385,2M =5*6*11=330,3M 5*6*7=210.4M M =1(modm )，i=1,2,3,4i i i得M =3 M =1 M =1 M =1，2.解一次同余式组x 三 3(mod8)x三 ll

9、(mod20)x 三 l(modl5)解：由于m =8,1m =20，2m =15，两两不互质，3就不能用孙子定理了，要用引理2 求解(m， m )=(8， 20)=22|8=b -b1221(m2， m ) =(20， 15) = 5 35|10=b -b23m1 ，m3) =(8，15) =11|2=b1-b3则同余式组有解。m =8=23，m =20=22 *5，m =l5=3*5，l23m= m , m , m ,m =23 *5*3=120l 23 k取 m = 23 =8, m =5, m、=3l23显然 m T m , j=1,2,3且 m, m , m、两两互质，则 m= m、

10、m、mj jl 23l 23原同余式与同余式 x=3(mod8)x=11(mod5)x=1(mod13)同解，由于m =8, m =5, m =3两两互质，可以用孙子定理求解123m=23*5*3=120，M1=5*3=15,M = 8*3=24,2M =58*5=40,3M M =1(modm ), i=1,2,3,4i i i则M = - 1 M =- 1 M =1123八x三(-1) *15*3+ (- 1) *24* 11+1 *40*1 三-29三91 (mod120) 参考文献：【1】严士健，初等数论第三版，2003年7月第3版，【M】2,定理1【 2】江西科技师范学院，数学与计算机科学学院，数学与应用数学专业初等数 论内部资料【3】严士健，初等数论第三版，2003年7月第3 版,【M】2,例题2