中国剩余定理(CRT)：求解模线性方程组

2019-04-13 14:46发布

站内文章 / 模拟电子
11878 0 1359

定义

 设有同余式组 (S)：
(S)：⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪x≡a1(modm1)x≡a2(modm2)x≡a3(modm3)⋮x≡ak(modmk)
即
x≡ai(modmi),i=1,2,..,k
 其中 ai 和 mi 已知，且当i≠j 时， 有 (mi,mj)=1 , 求x对模 m1m2...mk 的解。

解的情况

 有唯一解， 证明略。
 下面会构造出此解，然后证明其正确性和唯一性。
 设
M=∏ki=1mi//即所有m的积 Mi=Mmi//即除mi以外所有m的积 //M−1i为Mi的逆元(对模mi)，即MiM−1i≡1(modmi)
 则(S)的解为:
x=tM+∑i=1kaiMiM−1i
即
x=(∑i=1kaiMiM−1i)(modM)
 下证其正确性:
我们考查任一在[1, k]内的第i项:

热门文章