中国剩余定理：求解同余方程组的高效方法

定义11.8 设f（x）=a_mx^m+…+a₁x+a₀是整系数多项式，称

f（x）≡0（mod n）且a_m（mod n）≠0

是模n的m次同余方程。满足方程的整数x称为方程的解。

中国剩余定理是约公元前100年时由中国数学家孙子发现的，故也称为孙子定理。它是数论中最有用的定理之一。

定理11.13 （中国剩余定理）设自然数m₁，m₂，…，m_r两两互素，记M=m₁m₂…m_r，则同余方程组

在模M同余的意义下有唯一解

证明：因为m₁，m₂，…，m_r两两互素，M_i=m₁，m₂，…，m_i-1，m_i+1，…，m_r，所以gcd（M_i，m_i）=1，M_i关于模m_i的乘法逆元存在，设为y_i，则有

M_iy_i≡1（mod m_i），从而b_iM_iy_i≡b_i（mod m_i）（i=1，2，…，r）

又因为m_i|M_j≠i，故

令

则x₀是以上同余方程组的解。

下面证明模M下的唯一性。

假设以上方程组有两个解x₁，x₂，则对任意的i，有

x₁≡b_i（mod m_i），x₂≡b_i（mod m_i），故x₁-x₂≡0（mod m_i）

即

m_i|（x₁-x₂）（i=1，2，…，r）

因

M=m₁m₂…m_r

所以

M|（x₁-x₂），x₁-x₂≡0（mod M），x₁≡x₂（mod M）(www.xing528.com)

即在模M下两个解x₁，x₂相同。

【例11-24】 对于同余方程组

M=2×3×5=30，M₁=15，M₂=10，M₃=6

15y₁≡1（mod 2）得y₁=1

10y₂≡1（mod 3）得y₂=1

6y₃≡1（mod 5）得y₃=1

则该方程在模M下的解为

x=1×15×1+2×10×1+3×6×1=53≡23（mod 30）

【例11-25】 求解同余方程组

【解析】 由中国剩余定理可知

m₁=3，m₂=5，m₃=7，m₄=11

M=3×5×7×11=1155

M₁=5×7×11，M₂=3×7×11，M₃=3×5×11，M₃=3×5×7

（5×7×11）y₁≡1（mod 3）得y₁=1

（3×7×11）y₂≡1（mod 5）得y₂=1

（3×5×11）y₃≡1（mod 7）得y₃=2

（3×5×7）y₄≡1（mod 11）得y₄=2则该方程在模M下的解为

x≡b₁M₁y₁+b₂M₂y₂+…+b₄M₄y₄（mod M）≡2×（5×7×11）×1+4×（3×7×11）×1+5×（3×5×11）×2+

6×（3×5×7）×2（mod 1155）≡770+924+1650+1260（mod 1155）≡1139（mod 1155）