中国剩余定理

1 中国剩余定理 中国剩余定理（Chinese Remainder Theorem），古称韩信点兵，是整数论里一个非常重要的法则。大约在三国到魏晋南北朝之间（公元280 ~ 473 年）有一本数学古书「孙子算经」问世，这个孙子与着孙子兵法的孙武无关。「孙子算经」有这样的问题：「今有物，不知其数，三三数之，剩二，五五数之，剩三，七七数之，剩二，问物几何？」 这是一个典型的余数问题：有一个正整数被 3 除余数为 2，被 5除余数为 3，被 7 除余数为 2，则此数最小为多少？ 孙子算经上也有如下的答案与解法： 答曰：「二十三」 术曰：「三三数之剩二，置一百四十，五五数之剩三，置六十三，七七数之剩二，置三十，并之，得二百三十三，以二百一十减之，即得。凡三三数之剩一，则置七十，五五数之剩一，则置二十一，七七数之剩一，则置十五，即得。」 孙子算经的解法其实也是现今数论证明的内涵，因为其解法远在一千五百年前就已经为中国人发现，故名中国剩余定理。 先故虑被 3 除余数为 1 的数： 将 5 乘以 7 得 35 求 35x 被 3 除余1（或135x被 3 整除）的 x 之解 2 解得2x（7 023 5﹐7 0 被3 除余数为1 ） （此地x 的解有很多，取其最小正整数即2 ） 也就是说7 0 被3 除余数为1 （而7 0 同时被5 与7 整除） 所以 27 0  被3 除余数为2 即 1 4 0 被3 除余数为2 （而1 4 0 同时也被5 与7 整除。） 再故虑被5 除余数为1 的数： 将 3 乘以7 得2 1 求 2 1 x 被5 除余数为1 的x 之解 解得1x﹐2 12 1x 故 2 1 被5 除余数为1 ﹐ 而32 1  被5 除余数为3 ﹐ 即6 3 被5 除余数为3 （而6 3 同时也被3 与7 整除） 最后故虑被7 除余数为1 的数： 将53  得1 5 求 1 5 x 被7 除余数为1 的x 之解 解得1x﹐而1 51 5x 故 1 5 被7 除余数为1 因此21 5  被7 除余数为2 即3 0 被7 除余数为2 （而3 0 同时也被3 与5 整除） 3 再将140、63、30 加起来得 2333063140 因为 63 与 30 都被 3 整除，而 140 被 3 除余 2，故 233 被 3 除余数还是 2； 因为 140 与 30 都被 5 整除，而 63 被 5 除余 3，故 233 被 5 除余数还是 3； 因为 140 与 63 都被 7 整除，而 30 被 7 除余 2，故 233 被 7 除余数还是 2。 因此 233 满足题目所设的...