中國餘數定理和韓信點兵

來源: 泥中隱士 2019-10-13 03:36:28 [] [博客] [舊帖] [給我悄悄話] 本文已被閱讀: 次 (3813 bytes)
本文內容已被 [ 泥中隱士 ] 在 2019-10-13 03:44:19 編輯過。如有問題,請報告版主或論壇管理刪除.

在基礎數論裏有一個中國餘數定理。給定一組正整數兩兩互素,也就是任意兩個數沒有大於一的公因子。現有一個未知數,它除以這個數組裏每個數的餘數是知道的,求解這個未知數。中國餘數定理是對這個問題的解答。

中國古代最有名的數學書“九章算術”裏有一個問題:求知一個數,它除3餘2,除5餘3,除7餘2.。書上沒有給出這種問題的一般解法,但找出23這個數並不是很難。 很多科普文章說這個問題的提出源自“韓信點兵”:韓信讓一群士兵分別站成三人一排,五人一排,七人一排。每次站隊時可能會有餘下的士兵。從這三個餘數就能知道這一群士兵有多少人。

讓我們來仔細看看這個過程,檢查一下韓信點兵裏可能會出現的問題。首先如果兩個數除以三,五,七的餘數是相同的,則兩數之差可以整除三,五,七,因而就能整除這三個數的乘積一百零五。反之如果兩數之差可以整除一百零五則它們除以三,五,七的餘數是同樣的。因而僅僅從三個餘數無法唯一確定未知數。首先必須確定這個未知數在一個差別小於一百零五的範圍,例如從一到一百零五,從兩千三百到兩千四百零四。

下麵我們假定一個等於一百零五的範圍給定了。任意一個在這個範圍裏的數除三會有三個可能的餘數,除五會有五個可能的餘數,除七會有七個可能的餘數,當然包括零餘數。三個餘數的所有可能剛好是一百零五。因而從三個餘數可以唯一確定未知數。 那麽怎樣從這三個餘數決定未知數呢?有公式說從70m + 21n + 15p加減一百零五的適當倍數就能得出未知數。這裏m,n,p是未知數除以三,五,七的餘數。還可以列個表把每個數和它的三個餘數列成四個數字一行的表,然後按照餘數的順序重新列表好從三個餘數查出未知數。

以未知數在一到一百零五為例。如果三個餘數都為零未知數是一百零五。如果三個餘數不都為零未知數是70m + 21n + 15p除以一百零五的餘數。當然如果70m + 21n + 15p是在一到一百零四之間它就是未知數。在m=2,n=3,n=2時, 70m + 21n + 15p=233。然後把233除以105得到餘數23。也可以列表第一行為 0, 0, 1, 15;第二行為 0, 0, 2, 30;一共一百零五行。 查表時則以餘數為序從 2,3,2,23那一行得知未知數為23。

如果未知數是在兩千三百到兩千四百零四之間,我們得把233加上2100得到2333這個數。查表的話,先得列個表把一百零五種可能的餘數列出,後麵列出有關的未知數。

那麽韓信在點兵知道三個餘數後能不能一口報出士兵的人數呢?假如他知道人數不超過105,則看一下表他的確就能一口報出。要是用公式算則要費點功夫。要是人數多但在一個差105的範圍內,查表也可以, 當然要多費點功夫。用公式算就更費功夫了。

無論是查表還是用公式,韓信應該都是能做到的。列個表帶在身邊不是很難的事。至於他如何得到公式我們不清楚。但70,21,15是很特別的數,它們的餘數分別為1,0,0;0,1,0;0,0,1。一旦他知道了公式記住用就行了。

韓信沒有帶過兵和同時代的古羅馬軍隊作戰。韓信沒法向他們學學更好的點兵法。古羅馬的軍隊列成10人一排以十排作為一個方陣。如果不到一百人,數一下有幾排人後再數餘下的人數。點兵對於古羅馬人是個很簡單的事。

所有跟帖: 

羅馬人聰明,世到如今羅馬人在那裏?還有幾個人識得羅馬數字?差不多是絕頂啊。 -走石飛沙- 給 走石飛沙 發送悄悄話 走石飛沙 的博客首頁 (0 bytes) () 10/13/2019 postreply 08:25:24

三人同行七十稀,五樹梅花廿一枝,七子團圓正半月,除百零五便得知。這個你聽說過吧? -yma16- 給 yma16 發送悄悄話 yma16 的博客首頁 (0 bytes) () 10/13/2019 postreply 09:11:35

要是有時間數排數,還算什麽算? 韓信點兵的優點就是不用數排數。 -coolwin- 給 coolwin 發送悄悄話 coolwin 的博客首頁 (0 bytes) () 10/13/2019 postreply 10:12:42

羅馬的方陣不是為了“點“兵,而是為了作戰。而且一個羅馬方陣不是100人,而是60-160人。再說點兵的意思是數人頭嗎? -白雲藍天- 給 白雲藍天 發送悄悄話 白雲藍天 的博客首頁 (0 bytes) () 10/13/2019 postreply 12:25:42

所謂點兵,就是現在”閱兵“的意思。不是數人頭,人頭數自有人上報上來,而不用將帥一個一個地去點。 -白雲藍天- 給 白雲藍天 發送悄悄話 白雲藍天 的博客首頁 (0 bytes) () 10/13/2019 postreply 12:27:55

十進製是中國最早發明的。至少在商代,中國已采用了十進製。商代陶文和甲骨文中,已有一到十、百、千、萬等數字。 -白雲藍天- 給 白雲藍天 發送悄悄話 白雲藍天 的博客首頁 (0 bytes) () 10/13/2019 postreply 12:53:35

請您先登陸,再發跟帖!