关于中国剩余定理的问题

mathck

------------------------------------------------------------
例子：计算下面的方程（中国剩余定理）：
x=2 mod 3
x=3 mod 5
x=2 mod 7

以上3个式子的等号都是3个横线的（电脑没法打该字符）
------------------------------------------------------------

解法：
1）M = 3 * 5 * 7 = 105
2）M1= 105/3 = 35, M2 = 105/5 = 21, m3 = 105/7 = 15
3）M1的乘法逆 = 2，M2的乘法逆 = 1，M1的乘法逆 = 1
4）x = (2*35*2 + 3*21*1 + 2*15*1) mod 105 = 23 mod 105

即结果为 x = 23

-------
问题：
-------
1）上面3）中的 “M1的乘法逆”、“M2的乘法逆”、“M3的乘法逆” 是如何计算出来的？

mathck

顶.............

mathck

ding.............................

mathck

有人知道吗？

elim

可以用辗转相除法得到.

12x3 - 35 = 1,  

(12-35k)3 +(3k-1)35 =1,  

M1 的乘法逆就是 3k-1 的最小正值 2

以下是中国剩余定理的证明，含有你的问题的解答和证明

luyuanhong