標籤:科技

中國古代著名算題。原載《孫子算經》卷下第二十六題:「今有物不知其數,三三數之剩二;五五數之剩三;七七數之剩二。問物幾何?」當時雖已有了答案23,但它的系統解法是秦九韶在《數書九章·大衍求一術》中給出的。大衍求一術(也稱作「中國剩餘定理」)是中國古算中最有獨創性的成就之一,屬現代數論中的一次同餘式組問題。

1歷史起源

這是依據《孫子算經》上有名的「孫子問題」(又稱「物不知數題」)編寫而成的。原來的題目是:
「今有物不知其數,三三數之剩二,五五數之剩三,七七數之剩二。問物幾何?」

2詳細內容

「今有物不知其數,三三數之剩二,五五數之剩三,七七數之剩二。問物幾何?」
用通俗的話來說,題目的意思就是:
有一些物品,不知道有多少個,只知道將它們三個三個地數,會剩下2個;五個五個地數,會剩下3個;七個七個地數,也會剩下2個。這些物品的數量至少是多少個?
(註:詩題及題目原文都無「至少」二字,但「孫子問題」都是些求「最少」或者求「至少」的問題,否則就會有無數多個答案。所以,解釋題目意思時,在語句中加上了「至少」二字。)
《孫子算經》解這道題目的「術文」和答案是:
「三三數之剩二,置一百四十;五五數之剩三,置六十三;七七數之剩二,置三十。並之,得二百三十三,以二百十減之,即得。」「答曰:二十三。」
這些話是什麼意思呢?用通俗的話來說,就是:
先求被3除餘2,並能同時被5、7整除的數,這樣的數最小是35;
再求被5除餘3,並能同時被3、7整除的數,這樣的數最小是63;
然後求被7除餘2,並能同時被3、5整除的數,這樣的數最小是30。
於是,由35+63+30=128,得到的128就是一個所要求得的數。但這個數並不是最小的。
再用求得的「128」減去或者加上3、5、7的最小公倍數「105」的倍數,就得到許許多多這樣的數:
{23,128,233,338,443,…}
從而可知,23、128、233、338、443、…都是這一道題目的解,而其中最小的解是23。
答:這些物品的數目至少是23個。
需要指出的是,在《孫子算經》上,有一段關於這類題目的解題「術文」:
「凡三三數之剩一則置七十,五五數之剩一則置二十一,七七數之剩一則置十五,一百六以上以一百五減之,即得。」
(註:古稱「106」和「105」為「一百六」和「一百五」,而稱「160」和「150」為「一百六十」和「一百五十」。所以,這裡的「一百六」和「一百五」分別指「106」和「105」,而不是「160」和「150」。)

3原理簡介

明代著名的大數學家程大位,在他所著的《演算法統宗》中,對於這種解一般「孫子問題」的方法,還編出了四句歌訣,名曰《孫子歌》:
三人同行七十稀,
五樹梅花廿一枝;
七子團圓正半月,
除百零五便得知。
歌中的「廿」,讀音與「念」音相同。「廿」即二十的意思。
這一歌訣的「詩意」,我們可以不去理會,只需注意它的數字就行了。歌訣中的每一句話,都指出了一步解題方法:
「三(3)人同行七十(70)稀」——是說除以3所得的餘數,要用「70」去乘它;
「五(5)樹梅花廿一(21)枝」——是說除以5所得的餘數,要用「21」去乘它;
「七(7)子團圓正半月(15)」——「半月」是一個月30天的一半,即15日,這是說,除以 7所得的餘數,要用「 15」去乘它;
「除百零五(105)便得知」——這是說要把上面所乘得的三個數相加,加得的和如果大於105,便應減去105,或者減去105的倍數。這也就是《孫子算經》上的「一百六(106)以上,以一百五(105)減之」。這樣得出的差,便是所要求的這個最小的未知數了。
運用這一歌訣來解答這道「物不知數」問題,便是
2×70+3×21+2×15=140+63+30=233
233-105-105=23(答略)

4特點

不過,用這種方法解這類問題,有它的局限性,它只能解答用3、5、7作除數的題目,遇到用其他數作除數的算題,它就行不通了。這一點必須引起我們的注意。

5理論發展

這種「物不知數(孫子)問題」,在中國古代流傳的演算法名稱很多。宋朝周宓稱它為「鬼谷算」、「隔牆算」(之所以稱「鬼谷算」,大概是因為它與傳說中的哲學家鬼谷子有某些關係);13世紀的大數學家楊輝則稱它為「剪管術」。南宋數學家秦九韶將它推廣,並又發現一種演算法,稱它為「大衍求一術」。它被傳入西方后,外國人又稱它為「中國剩餘定理」。但是大多數人較為通俗的叫法,還是稱它為「韓信點兵」(也有稱「秦王暗點兵」的)。傳說中國漢朝的大將韓信,計算士兵數目的方法十分特別,他不是五個五個或十個十個地數,也不要士兵「一、二、三、四、五……」地報數,而是叫他們排起隊伍,依次在他面前列隊行進:先是一排三人,再是一排五人,然後是一排七人。他只將三次所余的士兵記下來,就知道了士兵的總數。他旁邊的人見他並沒有數士兵的數目,有時甚至還閉上了眼睛,而居然知道士兵的總數,都感到十分驚奇。所以,後人就把這種演算法稱為「韓信點兵」了。「韓信點兵問題」在數學史上,是個極有名的問題。西洋人直到18世紀才被瑞士數學家歐拉發現這一問題的解題規律。只拿中國南宋秦九韶的研究與他們相比,他們也晚了五百年左右的時間。

6應用實例

在雷達領域中,中國剩餘定理被用在脈衝多普勒雷達上,解目標的距離模糊和速度模糊,在線天線陣接收雷達中解測角的模糊;在信號處理的理論中,基於中國剩餘定理的數論變化是一種重要的快速變換方法,只是目前還缺乏對其物理意義的描述而使其應用受到一定的限制;在IC設計中,應用中國剩餘定理可以獲得高效的IIR濾波器設計的方法;中國剩餘定理還奠定了目前世界上最流行的公鑰加密技術(即RSA)的基礎。
上一篇[AOC 416V]    下一篇 [極限思想]

相關評論

同義詞:暫無同義詞