中国剩余定理

512 浏览 0 回复 2019-11-18

段三园的小迷弟

+关注

给出条件：

一：m1,m2...mk两两互质

二：

$x\equiv a1\ (mod\ m1)$

$x\equiv a2\ (mod\ m2)$

....

$x\equiv a_k\ (mod\ m_{k})$

求x

令 $M=m_1m_2...m_k$

令 $M_i=M/m_i$ (与mi互质)（用exgcd求mi的逆）

所以可求 Mi模mi的逆（用exgcd求Mi*infMi=1（mod p））

则 $x=a_1M_1*M_1^{-1}+a_2M_2*M_2^{-1}...a_kM_k*M_k^{-1}$

证明上式：题意有 x=a1（mod m1）

按上式：x=a1*M1*infM1=a1 (mod m1) （其余的含m1被约掉）

中国剩余定理

评论加载中...