韓信點兵問題 3人一排餘2，5人一排餘3，7人一排餘2 算出

1樓：匿名使用者

中國剩餘定理

民間傳說著一則故事——「韓信點兵」。

秦朝末年，楚漢相爭。一次，韓信將1500名將士與楚王大將李鋒交戰。苦戰一場，楚軍不敵，敗退回營，漢軍也死傷四五百人，於是韓信整頓兵馬也返回大本營。

當行至一山坡，忽有後軍來報，說有楚軍騎兵追來。只見遠方塵土飛揚，殺聲震天。漢軍本來已十分疲憊，這時隊伍大譁。

韓信兵馬到坡頂，見來敵不足五百騎，便急速點兵迎敵。他命令士兵3人一排，結果多出2名；接著命令士兵5人一排，結果多出3名；他又命令士兵7人一排，結果又多出2名。韓信馬上向將士們宣布：

我軍有1073名勇士，敵人不足五百，我們居高臨下，以眾擊寡，一定能打敗敵人。漢軍本來就信服自己的統帥，這一來更相信韓信是「神仙下凡」、「神機妙算」。於是士氣大振。

一時間旌旗搖動，鼓聲喧天，漢軍步步進逼，楚軍亂作一團。交戰不久，楚軍大敗而逃。

在一千多年前的《孫子算經》中，有這樣一道算術題：

「今有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二，問物幾何？」按照今天的話來說：乙個數除以3餘2，除以5餘3，除以7餘2，求這個數.

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

① 有乙個數，除以3餘2，除以4餘1，問這個數除以12餘幾？

解：除以3餘2的數有：

2， 5， 8， 11，14， 17， 20， 23….

它們除以12的餘數是：

2，5，8，11，2，5，8，11，….

除以4餘1的數有：

1， 5， 9， 13， 17， 21， 25， 29，….

它們除以12的餘數是：

1， 5， 9， 1， 5， 9，….

乙個數除以12的餘數是唯一的.上面兩行餘數中，只有5是共同的，因此這個數除以12的餘數是5.

如果我們把①的問題改變一下，不求被12除的餘數，而是求這個數.很明顯，滿足條件的數是很多的，它是 5＋12×整數，

整數可以取0，1，2，…，無窮無盡.事實上，我們首先找出5後，注意到12是3與4的最小公倍數，再加上12的整數倍，就都是滿足條件的數.這樣就是把「除以3餘2，除以4餘1」兩個條件合併成「除以12餘5」乙個條件.

《孫子算經》提出的問題有三個條件，我們可以先把兩個條件合併成乙個.然後再與第三個條件合併，就可找到答案.

②乙個數除以3餘2，除以5餘3，除以7餘2，求符合條件的最小數.

解：先列出除以3餘2的數：

2， 5， 8， 11， 14， 17， 20， 23， 26，…，

再列出除以5餘3的數：

3， 8， 13， 18， 23， 28，….

這兩列數中，首先出現的公共數是8.3與5的最小公倍數是15.兩個條件合併成乙個就是8＋15×整數，列出這一串數是8， 23， 38，…，再列出除以7餘2的數 2， 9， 16， 23， 30，…，

就得出符合題目條件的最小數是23.

事實上，我們已把題目中三個條件合併成乙個：被105除餘23.

那麼韓信點的兵在1000-1500之間，應該是105×10+23=1073人

2樓：匿名使用者

首先找出能被5與7整除而被3除餘1的數70，被3與7整除而被5除餘1的數21，被3與5整除而被7除餘1的數15。

所求數被3除餘2，則取數70×2＝140，140是被5與7整除而被3除餘2的數。

所求數被5除餘3，則取數21×3＝63，63是被3與7整除而被5除餘3的數。

所求數被7除餘2，則取數15×2=30，30是被3與5整除而被7除餘2的數。

又，140＋63＋30=233，由於63與30都能被3整除，故233與140這兩數被3除的餘數相同，都是餘2，同理233與63這兩數被5除的餘數相同，都是3，233與30被7除的餘數相同，都是2。所以233是滿足題目要求的乙個數。

而3、5、7的最小公倍數是105，故233加減105的整數倍後被3、5、7除的餘數不會變，從而所得的數都能滿足題目的要求。由於所求僅是一小隊士兵的人數，這意味著人數不超過100，所以用233減去105的2倍得23即是所求。