M1’M1mod m1=1M1’M1=km1+1M1’M1+k’m1=1
(M1,m1)=1最大公约数为1，M1’,k’为组合系数 利用辗转相除法求最大约数,然后求组合系数。
462=92*5+2 5=2*2+1 1=5-2*2
1=5-(462-92*5)*2 462*(-2)+5*(1+2*92)=1
证明:验证x满足方程
(mi,m1)=1,(mi,m2)=1,... (mi,mi-1)=1 (mi,mi+1)=1…(mi,mk)=1 (mi,m1m2...mi-1mi+1…mk)=1 ….(1) (mi,Mi)=1 故 Mix mod mi=1 有解Mi’ MiMi’ mod mi=1 从(1)可知当ji时 mj|Mi则 Mi mod mj=0
462*(-5+3)+ 5*(1+2*92)=1
462*3+5*(1+2*92-462)=1M1’=3
例3 x mod 5=1 x mod 6=5 x mod 7=4 x mod 11=10
x=(M1’M1b1+M2’M2b2+M’3M3b3 +M’4M4b4)mod m
=(462*3*1+385*1*5+330*1*4+210*1*10)mod m =6731 mod 2310=2111 mod 2310=2111
x mod 7=2
x mod 11=1 求x mod 77=?
m1=7 m2=11 m=m1*m2=77
M1=m/m1=11 M2=m/m2=7
解二 77=7*11 x=21000000,x mod 77=? x mod 7=2 x mod 11=1 求x mod 77=? m1=7 m2=11 m=m1*m2=77 M1=m/m1=11 M2=m/m2=7 M1M1’ mod m1=1 M1的逆元 M2M2’ mod m2=1 M2的逆元 11M1’ mod 7=1 M1’=2=11 (7)-1mod 7 =115 mod7 7M2’ mod 11=1 M2’=8=7 (11)-1mod 11 =79 mod11 x=(M1M1’b1+M2M2’b2)mod m=
x1mod m=x2 mod m x1,x2同属一个同余类，即是同一解。
21000000mod 77=?
解二 77=7*11 x=21000000,x mod 77=?
x mod 7=b1 x mod 11=b2 this!1
b1,b2可求出，问 x mod 77=?
2(7) 261 mod 7
例2
x mod 5=b1
x mod 6=b2
x mod 7=b3
x mod 11=b4
m1=5 m2=6 m3=7 m4=11 m=m1m2m3m4=56711 M1=m/m1= 6711=462 M1’=Mi(mi)-1mod mi=3 M2=m/m2=5711=385 M2’=Mi(mi)-1mod mi=1 M3=m/m3=5611=330 M3’=Mi(mi)-1mod mi=1 M4=m/m4=567=210 M4’=Mi(mi)-1mod mi=1
例: x mod 3=2 x mod 5=3 x mod 7=2
m1=3 m2=5 m3=7 b1=2 b2=3 b3=2 m=m1m2m3=357 M1=m/m1=57 M1’=Mi(mi)-1mod mi=2 M2=m/m2=37 M2’=Mi(mi)-1mod mi=1 M3=m/m3=35 M3’=Mi(mi)-1mod mi=1 x=(M1’M1b1+M2’M2b2+…+M’kMkbk )mod m =(2*5*7*2+1*3*7*3+1*3*5*2)mod 105 =(140+63+30) mod 105=233 mod 105=23
(M1’M1a1+M2’M2a2+…+M’jMjaj+...+M’kMkak )
mod mj=M’jMjajmod mi=ajmod mi. x mod mi=ai mod mi 即满足方程。
证明:惟一性，同一等价类的数看成一个根 若x1,x2均是方程的根,
x1 mod mi=ai mod mi=x2 mod mi m=m1m2.. mk 又m1,m2,…,mk两两互素 则
中国剩余定理
今有物不知其数，三三数之有二，五五 数之有三，七七数之有二，问物有多少？ 解答：三三数之有二对应140，五五数之有 三对应63，七七数之有二对应30，这些数 相加得到233，再减210，即得数23。 同余方程式：
x mod 3=2 x mod 5=3 x mod 7=2 2572=140 1373=63 1352=30 2 357=210
x=(M1’M1b1+M2’M2b2+M’3M3b3 +M’4M4b4)mod m =(462*3*b1+385*1*b2+330*1*b3+210*1*b4)mod m
x mod 5=b1 x mod 6=b2 x mod 7=b3
x mod 11=b4 m1=5 m2=6 m3=7 m4=11 M1=m/m1= 6711=462 M1’M1mod m1=1 M2=m/m2=5711=385 M2’M2mod m2=1 M3=m/m3=5611=330 M3’M3mod m3=1 M4=m/m4=567=210 M4’M4mod m4=1
复习
Mi=m/mi MiMi’ mod mi=1 显然(Mi,mi)=1
即Mi’是Mi的逆元Mi(mi)-1mod mi或者可用
辗转相除法求Mi’.
定理4: mZ+, aZ,a是模m简化剩余的充要 条件a是模m的可逆元。 必要性:a简化剩余则a可逆
a简化剩余(a,m)=1ax mod m=1有惟 一解a’,即aa’ mod m=1a是可逆元。 充分性:a可逆则a是简化剩余 a可逆存在a’，使得aa’ mod m=1 则方程ax mod m=1有解，根据定理1的必 要可知(a,m)|b即 (a,m)|1 故 (a,m)=1
=(11*2*2+7*8*1)mod m=23
Euler Th.
1000000=166666*6+4

X=21000000=2166666*6+4=(26)16666624 2 mod 7
2(11) 2101 mod 11
Euler Th.
1000000=100000*10
X=21000000=2100000*10=(210)100000 1 mod 11
定理1 设m1,m2,…mk是两两互素的正整数，
则对任意b1,b2,…,bk，同余方程组
x mod m1=b1 mod m1,
x mod m2=b2 mod m2,
…
x mod mk=bk mod mk, 其解为：
x=(M1’M1b1+M2’M2b2+…+M’kMkbk )mod m
m=m1m2…mk,