《中国剩余定理的算法.docx》由会员分享，可在线阅读，更多相关《中国剩余定理的算法.docx（5页珍藏版）》请在三一文库上搜索。
1、中国剩余定理的算法于宗江1. 两个数的情况 , 即 Mr1modm1(m1m2 ) .r2modm2解：题设隐含要求:M0, m1, m20, 0rimi ,(i 1,2) ,r1r 20. 如果r1 r20, 那么M0.显然 , 最小的 M 必定满足 Mm1 m2 .如果 Mm1 m2 ,那么 Mm1m2M 同样满足上述要求 , 这与 M 为最小矛盾. 同时如果Mm1m2 ,那么 M 必定为最小. 反设存在0 M 'M 满足上述条件 ,则 MM ' 将同时被 m1 , m2 整除 , 即 MM ' 是 m1 , m2 的公倍数 , 又因为 m1 , m2 互素 , 那
2、么 MM 'km1 m2 , (k) .这与 Mm1m2 矛盾 .m1 x1r1 r2m2 x2 , 记为 m1 x1r11m2 x2 .则, m2 整除 m1 x1 r11 .按照如下方式对m1x1r11 进行运算 (运算过程中要始终确保未知系数xi , xij0 , 否则最小值就无从谈起 ). r110则 Mr1 r2 r110记 m1m11 mod m2 , (0m11m2 ) ,r11r11' mod m2 , (0r11'm2 ) .因为 m1 , m2 互素 , 故 m110 .则, m11 x1 r11'm2 x21 .现要证明 x1 , x2 的
3、最小值与 x1 ,x21 的最小值等价 .即 m1 x1r11m2 x2m1m2m11x1r11'm2 x21m11m2 .由 m1 x1r11m2 x2m1m2 可得 ,x1m2 , 因为 x1 ,m2为整数 ,所以 x1m21 .于 是 ,m11 x1r11'm11 (m21) m2(m111)m2m11 , 又 因 为 m11 x1r11'm2 x21 ,我们得到 m11 x1r11'm2 x21m11m2 .反之 , 由 m11 x1r11'm2 x21m11m2 可得 , 如果 r11'0 , 那么 x1 , x210 ,因此 m1 x
4、1r11m2 x2 r11m1m2 ; 如果 r11'0 ,那么 x1m2 , 又因为 x1 ,m2为整数 ,所以 x1m21 , 于是 , m1 x1r11 m2 x2 m1 (m21) m1m1m2 .得证 . r110注由 r11的定义可知 ,r11m1 .注 r11m2的情形只会出现在计算过程中, 而不会出现在整个运算的开始. 对于r11m2 的情形 ,只需把 m11 x1 r11m2 x21改写为 m11x1m2 x21r11 这样的形式 , 即变换为的情形 .注之所以 m2r11'0 , 是为了确保 m11 x1r11'm2 x21 与 m1 x1r11m2
5、 x2 同号 , 这样 x1 , x2 的最小值与x1 ,x21 的最小值才能等价.记 m1m11 modm2 , (0m11m2 ) , r11r11' mod m2 ,(m2r11'0) .则, m11 x1r11'm2 x21 .现要证明 x1 , x2 的最小值与 x1 ,x21 的最小值等价 .即 m1 x1r11m2 x2m1m2m11 x1 r11'm2 x21m11m2 .m1 x1m1m1 x1r11m1 m2 , 即 m1 (x11) m1m2 .则, x11 m2 ,即 x1m2 .于是 , m11x1r11'm11m2r11
6、9;m11m2 .反之 , m11x1r11'm2 x21m11m2 , m11 x1m2m11 x1r11'm11m2则, m11 x1m11( m21) , 于是 x1m2 1 .因此 , m1 x1r11m1m2m1r11', 又因为 m1 x1r11m2 x2 , r110 .所以 , m1 x1r11m2 x2m1m2 .再令 m1m2 , r11r11' , m2m11 , 即与辗转相除法类似, 用上一步的除数作为新的被除数 ,上一步中被除数的余数作为除数, 上一步中余数的余数的相反数作为新的余数, 如此反复 , 直到出现新产生的除数为1,停止 .根
7、据辗转相除法, 这是必定会出现的, 因为 m1 ,m2 互素 . 然后进入 ”补充证明 ”一段 , 即可得到答案 .得证 .例： M6mod82mod58x 6 5 y 28x 4 5y3x45y13x5y143x12y11 3x11 2 y1x1 1 2y2则易得 ,x11 ,y12,x2 ,M22.验证 :M225840 .结果正确 .1' . 满足题目条件的M形式为 MM mink ' m1 m2 .证明 :M 将同时被 m1 , m2整除 .2. 对于三个及三个数以上的情形, 即N个数的情形 .r1modm1Mr 2modm2(m1m2. mN ) .rNmod mN先
8、对 m1 , m2 , r1 , r2进行 1 中的运算 , 然后将 m1m2 作为新的 m2 , M 12 作为新的 r2 , 则成功的将 N 个数的情形转化为了N1个数的情形 .7 mod9例: M1 mod 5 . 2 mod 49x75 y19 x65y4x 1 5 y14x5 y1 14x1y1 14x11y1x21y1则,x20 ,y1,x1,M16 .1于是 , 例题等价于 M16mod452mod.445 x164 y245x144yx24 y1x4y12x1y1 1x11y1则,x10 ,y11 ,x2 ,M106 .补充证明设 b0.ax b y ax 1 y11 , 即
9、y b结论是显然的 .ax b y ax 1 y10 ,即 y a b根据运算过程 ,显然 ba, 因为 b 是前一步运算 moda 后的余数 . 因此 , 结论显然成立 .x ay bx1y 1 1 , 即 x b结论显然成立 .x ay bx1y 1 0 , 即 x a b根据运算过程 ,显然 ba, 因为 b 是前一步运算 moda 后的余数 . 因此 , 结论显然成立 .3. 两个数不互素的情况 , 题设与 1 相同 , 区别在于 m1 , m2 不互素 .算法与 1 相同 , 区别在于最后的验证求值 , 即 1 中的 ”补充证明 ”. 在 1 中的情况下 , M 的值必定存在 , 故
10、最小值也必定存在 . 而在 3 中的情况下 , M 的值未必存在 , 最小值也就无从谈起.因为1 中的算法实际就是辗转相除法, 而根据辗转相除法, 当两个数不互素时, 最终会形得到如下结果( 只讨论x 记号 ,y的情况类似),axb,其中a 为 m1 与m2 的最大公约数,aba ,当且仅当b0 或者ba 时 ,方程有解,分别为0 和1,再按照1 中的方法逆向代回 , 即可求得最小值 .而M 的通解则为 M Mmink' m1 m2 , 其中a为 m ,m的最a12大公约数 .三个及以上个数不互素的情形, 只需将 2 中新的 m2 更改为 m1 m2 即可 , 其中 a 为 m1 , m2 的a最大公约数 .