一次同余式组的解法

学 术 论 文

一次同余式组的解法

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 Residue theorem to solve, how should that manage? We will reveal in the example solution.

关键字:一次同余式组 模 孙子定理

[Key words] A congruence group Mold Residue theorem 正文：

引理1. （孙子定理）设m，m………. m是k个两两互质的正数，12k

m=m1m2......mk, m=miMi, i=1,2,…,k,则同余式组x≡b1(modm1),x≡b2(modm2)，…，x≡bk(modmk)的解为：

x≡M`

1M1b1+M`

2M2b2+…+M`

kMkbk(modm）,……(2)，

其中M`

iM≡1（modmi）,i=1,2,…,k.

证明：由（mi，mj）=1，i≠j 即得（Mi，mi）=1，故由§1定理即知对每一Mi，有一M`

i存在，使得M`

iMi≡1（modmi）.

另一方面m=miMi,因此mj|Mi，i≠j，故

M

j 1k`jMjbj≡M`iMibi≡bi（mod mi）即为（1）的解。

若x1,x2是适合（1）的任意两个整数，则

x1≡x2（mod mi）, i =1,2,…, k,

因（mi，mj）=1，于是x1≡x2（mod m），故（1）的解只有（2） 完【1】 引理2 . 设所给的一次同余式组为：

X≡b1(modm1)

X≡b2(mod m2)

…

X≡bk(mod mk)

（ⅰ）取m=[m1,m2,m3,…mk],则所给同余式组有解的充要是:

（mi,mj）|（bi bj）1 i≠j k,

且若有解，则对模m的解数为1（m1m2…mk未必两两互质）

（ⅱ）找出一组正数m1`,m`2,…mk`满足m`

j|mj，1 j k,且m1`,m`2,…mk`两两互质，

m=m1`m`2mk`

（ⅲ）若同余式组

X≡bj（mod mj）1 j k

有解，则它的解与同余式组X≡bj（mod m`j）1 j k同解，再用引理1求解。 证明：（ⅰ）充分性：对k用数学归纳法证明

①当k=2时，显然成立。

②假设当k=n时，在所给条件满足的情况下，相应的n个同余式组成的同余式有解，当k=n+1时，所给同余式组为：

X≡bi(modmi) i=1,2,…，n,n+1

且满足条件（mi,mj）|（bi bj）i，j=1,2,…，n,n+1

必要性：我们证明在这些条件下，此同余式组有解。

由于(mn,mn 1)|(bn,bn 1).

则X≡bn(modmn) X≡bn 1(modmn 1)有解

设x=ck是适合这两个同余式的一个整数，则适合其的一切整数可由

X≡cn(mod[mn,mn 1])

表出。下面考虑如下n个联立同余式

X≡bi(modmi) i=1,2,…，n-1

X≡cn(mod[mn,mn 1])

对于这个同余式组，我们有（mi,mj）|（bi bj）i，j=1,2,…，n-1

又cn≡bn(modmn)

cn≡bn 1(modmn 1)

bi≡bn(mod(mi,mn))

bi≡bn 1(mod(mi,mn 1))

故bi≡cn(mod(mi,mn))

bi≡cn 1(mod(mi,mn 1))

则bi≡cn(mod[(mi,mn),(mi,mn 1)])

又[(mi,mn),(mi,mn 1)]=（mi，[mn,mn 1]）i=1,2,…，n-1

这样一来，上述新的同余式组就满足如下条件：

bi≡bj（mod(mi,mj)）i，j=1,2,…，n-1

bi≡cn(mod（mi，[mn,mn 1]）) i=1,2,…，n-1

于是，由数学归纳法假设这个同余式组有解，而它的解与原同余式组同解。 则当n=k+1时，原同余式组有解，则命题成立

（ⅱ，ⅲ）证明在（ⅰ）的过程中 【2】 例：1.韩信点兵：有兵一队，若列成五行纵队，则末行一人，成六行纵队，则末行五人，成七行纵队，则末行四人；成十一行纵队，则末行十人，求兵数。 解：由题意知，x≡1(mod5), x≡5(mod6), x≡4(mod7), x≡10(mod11)

此时m1=5，m2=6，m3=7，m4=11两两互质，可以用孙子定理求解，

则m=5*6*7*11=2310,

M1=6*7*11=462,

M2= 5*7*11=385,

M3=5*6*11=330,

M45*6*7=210.

M`

iMi≡1(modmi)，i=1,2,3,4

得M`

1=3 M`

2=1 M3`=1 M4`=1，

故x≡3*462*1+1*385*5+1*330*4+1*210*10≡6731≡2111（mod2310）. 【3】

2.解一次同余式组 x≡3(mod8)

x≡11(mod20)

x≡1(mod15)

解：由于m1=8，m2=20，m3=15，两两不互质，就不能用孙子定理了，要用引理

2求解

（m1，m2）=（8，20）=2 2|8=b2-b1

（m2，m3）=（20，15）= 5 5|10=b2-b3

（m1，m3）=（8，15）=1 1|2=b1-b3

则同余式组有解。

m1=8=23，m2=20=22*5，m3=15=3*5，

m=[m1,m2,m3,…mk]=2*5*3=120 3

取m`

1=23=8，m`

2=5，m`

3=3

显然m`

j|mj，j=1,2,3.且m`

1,m`

2,m`

3两两互质，则m=m`1m`

2m`

3

原同余式与同余式

x≡3(mod8)

x≡11(mod5)

x≡1(mod13)

同解，由于m`

1=8，m`

2=5，m`

3=3两两互质，可以用孙子定理求解

m=2*5*3=120， 3

M1=5*3=15,

M2= 8*3=24,

M3=58*5=40,

M`

iMi≡1(modmi)，i=1,2,3,4

则M`

1=–1 M`

2=–1 M3`=1

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