孙子定理和同余方程组

孙子定理和同余方程组 问题的提出 代数的主要问题就是解方程隋朝之前有部 孙子算经 提出 物不知数 问题 今有物不知数 三三数之有二 五五数之有三 七七数之有二 问物有几何韩信点兵有兵一队 若列成五行 末行一人 若列成六行 末行五人 列成七行 末行四人 列成十一行 末行十人 求兵数解决 大衍求一术 鬼谷算天文 历法的需要 孙子定理 明朝程大位 算数统筹 三人同行七十稀 五树梅花甘一枝 七子团圆整半月 除百零五便得知 孙子定理 利用算式表示 再把 233 105n均是答案 三人同行七十稀五树梅花甘一枝七子团圆整半月除百零五便得知 孙子定理 设m1 mk是k个两两互素的正整数 若令m m1 mk m miMi i 1 k 则对任意的整数b1 bk 同余方程组有唯一解其中 孙子定理 x 462 3 1 385 5 1 330 4 1 210 10 1 mod2310 6731 2111 mod2310 同余方程组 同余方程组有解的充要条件是 m1 m2 b1 b2 如果上述条件成立 则同余方程组模 m1 m2 有唯一解 证明设 m1 m2 d 先证必要性 若x0为同余方程组的解 则有x0 b1 modd x0 b2 modd 两式相减得b1 b2 0 modd 因此d b1 b2 再证充分性 若d b1 b2 则因x b1 modm1 的解可写为x b1 m1y 将其代入x b2 modm2 得m1y b2 b1 modm2 因为 m1 m2 d d b2 b1 故上式有解 即原同余方程组有解 设原同余方程组有两个解分别为x1和x2 则x1 x2 0 modm1 x1 x2 0 modm2 于是有x1 x2 0 mod m1 m2 即同余方程组模 m1 m2 有唯一解 同余方程组 练习解方程组 7x 5 mod18 13x 2 mod15 首先7x 5 mod18 化为 7x 5 mod2 和7x 5 mod9 即 x 1 mod2 和7x 5 mod9 13x 2 mod15 化为 13x 2 mod5 和13x 2 mod3 即 3x 2 mod5 和x 2 mod3 对于7x 5 mod9 可以推出7x 5 mod3 即x 2 mod3 所以只有3个 3x 2 mod5 x 1 mod2 和7x 5 mod9 解 x 4 2 2 9 1 1 5 9 2 1 5 2 209 29 mod90 系数都化为1 x 4 mod5 x 1 mod2 和x 2 mod9 孙子定理的应用 孙子定理的应用 求m 51675 mod1081 m 51675 46 5 22 30 15 515 5 257 5 27 20 32 4 mod23 m 51675 47 4 46 14 31 262 216 212 18 mod47 m 4 47 1 18 23 2 1063 65 mod1081 孙子定理 孙子定理的最大价值不在于直接解同余方程组而在于大模的一个同余式化为小模的 模互质的同余方程组然后利用欧拉定理 费马小定理将式子化简通过解同余方程组来提高解原来同余式的速度特别是存在大指数的情况更有效 法一 1012 127 8 4127 4 32 1所以 127 1012 1 有解1 4 32 1271 127 8 1012 32 127 127 255 1012 32所以127 255 1 mod1012 所以两边同乘以255255 127x 255 833 mod1012 907 mod1012 练习 解127x 833 mod1012 1012 4 11 23 所以化为方程组127x 833 mod4 化简为 x 1 mod4 127x 833 mod11 化简为 6x 3 mod11 x 5 mod11 127x 833 mod23 化简为 12x 5 mod23 x 10 mod23 对于第一个 M1 11 23 253因为253 1 mod4 M1 1对于第二个 M2 4 23 92因为92 4 mod11 M2 3对于第三个 M3 4 11 44因为44 2 mod23 M3 11求和 x 253 1 1 92 5 3 44 10 11 253 1380 4840 5967 907 mod1012 练习 解127x 833 mod1012 北大ACM网络热身赛 青蛙的约会两只青蛙在网上相识了 觉得很有必要见一面 它们很高兴地发现它们住在同一条纬度线上 于是它们约定各自朝西跳 直到碰面为止 青蛙们都是很乐观的 它们觉得只要一直朝着某个方向跳下去 总能碰到对方的 但是除非这两只青蛙在同一时间跳到同一点上 不然是永远都不可能碰面的 为了帮助这两只乐观的青蛙 你被要求写一个程序来判断这两只青蛙是否能够碰面 会在什么时候碰面 青蛙A和青蛙B 规定纬度线上东经0度处为原点 由东往西为正方向 单位长度