國剩余定理
民間傳說著一則故事——“韓信點兵”.
秦朝末年,楚漢相爭.一次,韓信將1500名將士與楚王大將李鋒交戰(zhàn).苦戰(zhàn)一場,楚軍不敵,敗退回營,漢軍也死傷四五百人,于是韓信整頓兵馬也返回大本營.當行至一山坡,忽有后軍來報,說有楚軍騎兵追來.只見遠方塵土飛揚,殺聲震天.漢軍本來已十分疲憊,這時隊伍大嘩.韓信兵馬到坡頂,見來敵不足五百騎,便急速點兵迎敵.他命令士兵3人一排,結(jié)果多出2名；接著命令士兵5人一排,結(jié)果多出3名；他又命令士兵7人一排,結(jié)果又多出2名.韓信馬上向?qū)⑹總冃迹何臆娪?073名勇士,敵人不足五百,我們居高臨下,以眾擊寡,一定能打敗敵人.漢軍本來就信服自己的統(tǒng)帥,這一來更相信韓信是“神仙下凡”、“神機妙算”.于是士氣大振.一時間旌旗搖動,鼓聲喧天,漢軍步步進逼,楚軍亂作一團.交戰(zhàn)不久,楚軍大敗而逃.
在一千多年前的《孫子算經(jīng)》中,有這樣一道算術(shù)題：
“今有物不知其數(shù),三三數(shù)之剩二,五五數(shù)之剩三,七七數(shù)之剩二,問物幾何?”按照今天的話來說：一個數(shù)除以3余2,除以5余3,除以7余2,求這個數(shù).
這樣的問題,也有人稱為“韓信點兵”.它形成了一類問題,也就是初等數(shù)論中解同余式.這類問題的有解條件和解的方法被稱為“中國剩余定理”,這是由中國人首先提出的.
① 有一個數(shù),除以3余2,除以4余1,問這個數(shù)除以12余幾?
除以3余2的數(shù)有：
2,5,8,11,14,17,20,23….
它們除以12的余數(shù)是：
2,5,8,11,2,5,8,11,….
除以4余1的數(shù)有：
1,5,9,13,17,21,25,29,….
它們除以12的余數(shù)是：
1,5,9,1,5,9,….
一個數(shù)除以12的余數(shù)是唯一的.上面兩行余數(shù)中,只有5是共同的,因此這個數(shù)除以12的余數(shù)是5.
如果我們把①的問題改變一下,不求被12除的余數(shù),而是求這個數(shù).很明顯,滿足條件的數(shù)是很多的,它是 5＋12×整數(shù),
整數(shù)可以取0,1,2,…,無窮無盡.事實上,我們首先找出5后,注意到12是3與4的最小公倍數(shù),再加上12的整數(shù)倍,就都是滿足條件的數(shù).這樣就是把“除以3余2,除以4余1”兩個條件合并成“除以12余5”一個條件.《孫子算經(jīng)》提出的問題有三個條件,我們可以先把兩個條件合并成一個.然后再與第三個條件合并,就可找到答案.
②一個數(shù)除以3余2,除以5余3,除以7余2,求符合條件的最小數(shù).
先列出除以3余2的數(shù)：
2,5,8,11,14,17,20,23,26,…,
再列出除以5余3的數(shù)：
3,8,13,18,23,28,….
這兩列數(shù)中,首先出現(xiàn)的公共數(shù)是8.3與5的最小公倍數(shù)是15.兩個條件合并成一個就是8＋15×整數(shù),列出這一串數(shù)是8,23,38,…,再列出除以7余2的數(shù) 2,9,16,23,30,…,
就得出符合題目條件的最小數(shù)是23.
事實上,我們已把題目中三個條件合并成一個：被105除余23.
那么韓信點的兵在1000-1500之間,應(yīng)該是105×10+23=1073人