如何解一次同余方程？

2025-02-25 17:19:50

推荐回答（5个）

回答1：

次同余式组模孙子定理
[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 . 设所给的一次同余式组为：
2/6
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])
3/6

对于这个同余式组，我们有（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，
4/6
故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）.