研究了一下“中國剩餘定理”之通解, 挺有意思

孫子問題與中國剩餘定理


    秦朝末年，楚漢相爭。一次，韓信將1500名將士與楚王大將李鋒交戰。苦戰一場，楚軍不敵，敗退回營，漢軍也死傷四五百人，於是韓信整頓兵馬也返回大本 營。當行至一山坡，忽有後軍來報，說有楚軍騎兵追來。隻見遠方塵土飛揚，殺聲震天。漢軍本來已十分疲憊，這時隊伍大嘩。韓信兵馬到坡頂，見來敵不足五百 騎，便急速點兵迎敵。他命令士兵3人一排，結果多出2名；接著命令士兵5人一排，結果多出3名；他又命令士兵7人一排，結果又多出2名。韓信馬上向將士們 宣布：我軍有1073名勇士，敵人不足五百，我們居高臨下，以眾擊寡，一定能打敗敵人。漢軍本來就信服自己的統帥，這一來更相信韓信是“神仙下凡”、“神 機妙算”。於是士氣大振。一時間旌旗搖動，鼓聲喧天，漢軍步步進逼，楚軍亂作一團。交戰不久，楚軍大敗而逃。

    在一千多年前的《孫子算經》中，有這樣一道算術題：
   “今有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二，問物幾何？”按照今天的話來說：一個數除以3餘2，除以5餘3，除以7餘2，求這個數.

    這樣的問題，也有人稱為“韓信點兵”.它形成了一類問題，也就是初等數論中解同餘式.這類問題的有解條件和解的方法被稱為“中國剩餘定理”，這是由中國人首先提出的.

 

例1、一個數除以3餘2，除以5餘3，除以7餘2，求符合條件的最小數.
解：（1）先列出除以3餘2的數：2， 5， 8， 11， 14， 17， 20， 23， 26，…，
（2）再列出除以5餘3的數：3， 8， 13， 18， 23， 28，….
這兩列數中，首先出現的公共數是8。
3與5的最小公倍數是15.兩個條件合並成一個就是8＋15×整數，
（3）列出這一串數是8， 23， 38，…，
（4）再列出除以7餘2的數 2， 9， 16， 23， 30，…，
就得出符合題目條件的最小數是23.

 

例2、有一個數，除以3餘2，除以4餘1，問這個數除以12餘幾？

解：（1）除以3餘2的數有：2， 5， 8， 11，14， 17， 20， 23….
（2）除以4餘1的數有：1， 5， 9， 13， 17， 21， 25， 29，….
（3）這兩列數中，首先出現的公共數是5。
3和4的最小公倍數是12，兩個條件合並成一個就是5＋12×整數
同時滿足兩個條件的數是5、17、29、……（依次增加12）
因此這個數除以12的餘數是5.


例3、今有物不知其數，二二數之餘一，四四數之餘三，五五數之餘二，七七數之餘三，九九數之餘四，問物幾何？

解：（1）九九數之餘四,可能的數是：13，22，31，40，49，58，……
（2）七七數之餘三,可能的數是：10，17，24，31，……
（3）這兩列數中，首先出現的公共數是31。
9和7的最小公倍數是63，兩個條件合並成一個就是31＋63×整數
（4）同時滿足上兩個條件的數有：31，94，157，220，283，346，409，472，535，598，661，724，787，……
（5）上列的數中，隻有157滿足五五數之餘二,
    5、7、9的最小公倍數是315，
（6）滿足上麵三個條件的數有：157，472，787，……
（7）隻有787滿足二二數餘一，四四數餘二。
所以，滿足條件的數最小的是787。


練習：
1、一個數除以3餘2，除以5餘3，除以7餘2，求滿足條件的最小數？
2、滿足除以5餘1，除以7餘3，除以8餘5的最小自然數。
3、在10000以內，除以3餘2，除以7餘3，除以11餘4的數有多少個？
4、求滿足除以6餘3，除以8餘5，除以9餘6的最小自然數。
5、一卷彩帶，如果剪成2分米或3分米或5分米或6分米都剩1分米，如剪成每段為7分米正好不剩。這卷彩帶至少多少米？
6、一個數除以5餘4，除以8餘3，除以11餘2，求滿足條件的最小的自然數。
7、有一堆蘋果，3個3個數餘1個，5個5個數餘2個，6個6個數餘4個。這堆蘋果至少有多少個？
8、在小於1000的自然數中，除以4餘3，除以5餘2，除以7餘4的最大自然數是多少？
9、在5000以內，除以3餘1，除以5餘2，除以7餘3的自然數有多少個
10、有一個兩位數，除以2與除以3都餘1，除以4與除以5都餘3，求這個數。