数论-孙子定理(中国剩余定理)及应用

x≡b1 (mod m1)

x≡b2 (mod m2)

......

x≡bk (mod mk)

例:

x≡2 (mod 3)   ①

x≡3 (mod 5)   ②

x≡2 (mod 7)   ③

由①,x=3*k+2  ④,代入②中得:

3*k+2 ≡ 3 (mod 5)

3*k≡1 (mod 5) 

k≡2 (mod 5)

∴k=5*l+2,代入④中得,x=15*l+8 ⑥

将⑥代入③中,得

15*l+6≡0 (mod 7)

5*l +2≡0 (mod 7)

l ≡ 1 (mod 7)

∴l = 7*n+1代入⑥中,得x=105*n+23

∴x最小为23

Th1:孙子定理(实在打不出来了>^<,放图)

 Th2:

一次同余式组

 x≡b1 (mod m1) ①

 x≡b2 (mod m2) ②

有解,当且仅当(m1,m2) | b2-b1,且有解时关于模[m1,m2]有唯一解

证明:

(必要性,有解->(m1,m2) | b2-b1)

∵①、②有解,故存在x0,有

x0≡b1 (mod m1)

x0≡b2 (mod m2)

设d=(m1,m2),则

x0≡b1 (mod d)

x0≡b2 (mod d)

∴0≡b2-b1 (mod d)

即b2≡b1 (mod d)

∴d=(m1,m2) | b2-b1

(充分性, (m1,m2) | b2-b1 -> 有解)

由①,x=m1*y+b1

故m1*y+b1≡b2 (mod m2)即m1*y+b1-b2 ≡0 (mod m2) ③

∵ (m1,m2) | b2-b1 ∴同余式③有解(根据定理:a*x≡b (mod p) 若想此同余式有解,当且仅当(a,p)|b

∴(两边同时除上d)(m1/d)*y+((b1-b2)/d) ≡ 0 (mod m2/d)

∵(m1/d,m2/d)=1,故存在y0(0≤y0≤m2/d)

有y=(m2/d)*t+y0(t=0,±1,±2...)

代入x=m1*y+b1中,得

x=(m1*m2)*t/d+m1*y0+b1(t=0,±1,±2...)

∴x≡C<m1*y0+b1> (mod [m1,m2])

注:孙子定理中要求模m1,m2,...,mk两两互素,若不互素,则如下:

x≡b1 (mod m1)

x≡b2 (mod m2)((m1,m2)≠1)

可算出x≡B (mod [m1,m2])

再将此式与其他式子组合,再计算其解

原文地址:https://www.cnblogs.com/jane315/p/13796621.html