中国剩余定理.ppt

中国剩余定理 今有物不知其数 三三数之有二 五五数之有三 七七数之有二 问物有多少 解答 三三数之有二对应140 五五数之有三对应63 七七数之有二对应30 这些数相加得到233 再减210 即得数23 同余方程式 xmod3 2xmod5 3xmod7 22 5 7 2 1401 3 7 3 631 3 5 2 302 3 5 7 210 定理1设m1 m2 mk是两两互素的正整数 则对任意b1 b2 bk 同余方程组xmodm1 b1modm1 xmodm2 b2modm2 xmodmk bkmodmk 其解为 x M1 M1b1 M2 M2b2 M kMkbk modmm m1m2 mk 复习Mi m miMiMi modmi 1显然 Mi mi 1即Mi 是Mi的逆元Mi mi 1modmi或者可用辗转相除法求Mi 定理4 m Z a Z a是模m简化剩余的充要条件a是模m的可逆元 必要性 a简化剩余则a可逆a简化剩余 a m 1 axmodm 1有惟一解a 即aa modm 1 a是可逆元 充分性 a可逆则a是简化剩余a可逆 存在a 使得aa modm 1 则方程axmodm 1有解 根据定理1的必要可知 a m b即 a m 1故 a m 1 例 xmod3 2xmod5 3xmod7 2m1 3m2 5m3 7b1 2b2 3b3 2m m1 m2 m3 3 5 7M1 m m1 5 7M1 Mi mi 1modmi 2M2 m m2 3 7M2 Mi mi 1modmi 1M3 m m3 3 5M3 Mi mi 1modmi 1x M1 M1b1 M2 M2b2 M kMkbk modm 2 5 7 2 1 3 7 3 1 3 5 2 mod105 140 63 30 mod105 233mod105 23 例2xmod5 b1xmod6 b2xmod7 b3xmod11 b4m1 5m2 6m3 7m4 11m m1 m2 m3 m4 5 6 7 11M1 m m1 6 7 11 462M1 Mi mi 1modmi 3M2 m m2 5 7 11 385M2 Mi mi 1modmi 1M3 m m3 5 6 11 330M3 Mi mi 1modmi 1M4 m m4 5 6 7 210M4 Mi mi 1modmi 1x M1 M1b1 M2 M2b2 M 3M3b3 M 4M4b4 modm 462 3 b1 385 1 b2 330 1 b3 210 1 b4 modm xmod5 b1xmod6 b2xmod7 b3xmod11 b4m1 5m2 6m3 7m4 11M1 m m1 6 7 11 462M1 M1modm1 1M2 m m2 5 7 11 385M2 M2modm2 1M3 m m3 5 6 11 330M3 M3modm3 1M4 m m4 5 6 7 210M4 M4modm4 1M1 M1modm1 1 M1 M1 km1 1 M1 M1 k m1 1 M1 m1 1最大公约数为1 M1 k 为组合系数 利用辗转相除法求最大约数 然后求组合系数 462 92 5 2 5 2 2 1 1 5 2 2 1 5 462 92 5 2 462 2 5 1 2 92 1 462 5 3 5 1 2 92 1 462 3 5 1 2 92 462 1 M1 3 例3xmod5 1xmod6 5xmod7 4xmod11 10 x M1 M1b1 M2 M2b2 M 3M3b3 M 4M4b4 modm 462 3 1 385 1 5 330 1 4 210 1 10 modm 6731mod2310 2111mod2310 2111 证明 验证x满足方程 mi m1 1 mi m2 1 mi mi 1 1 mi mi 1 1 mi mk 1 mi m1m2 mi 1mi 1 mk 1 1 mi Mi 1故Mixmodmi 1有解Mi MiMi modmi 1从 1 可知当j i时mj Mi则Mimodmj 0 M1 M1a1 M2 M2a2 M jMjaj M kMkak modmj M jMjajmodmi ajmodmi xmodmi aimodmi即满足方程 证明 惟一性 同一等价类的数看成一个根若x1 x2均是方程的根 x1modmi aimodmi x2modmim m1m2 mk又m1 m2 mk两两互素则x1modm x2modmx1 x2同属一个同余类 即是同一解 21000000mod77 解二77 7 11x 21000000 xmod77 xmod7 b1xmod11 b2this 1b1 b2可求出 问xmod77 2 7 26 1mod7EulerTh 1000000 166666 6 4X 21000000 2166666 6 4 26 16666624 2mod72 11 210 1mod11EulerTh 1000000 100000 10X 21000000 2100000 10 210 100000 1mod11xmod7 2xmod11 1求xmod77 m1 7m2 11m m1 m2 77M1 m m1 11M2 m m2 7 解二77 7 11x 21000000 xmod77 xmod7 2xmod11 1求xmod77 m1 7m2 11m m1 m2 77M1 m m1 11M2 m m2 7M1M1 modm1 1M1的逆元M2M2 mod