中國古代求解一類大衍問題的方法。大衍問題源於《孫子算經》中的“物不知數”問題:“今有物,不知其數,三三數之剩二,五五數之剩三,七七數之剩二,問物幾何?”這是屬於現代數論中求解一次同餘式方程組問題。宋代數學家秦九韶在《數書九章》(1247年成書)中對此類問題的解法作了系統的論述,並稱之為大衍求一術。德國數學家C.F.高斯是在1801年才建立起同餘理論的,大衍求一術反映了中國古代數學的高度成就。
中國剩餘定理民間傳說著一則故事——“韓信點兵”。秦朝末年,楚漢相爭。一次,韓信將1500名將士與楚王大將李鋒交戰。苦戰一場,楚軍不敵,敗退回營,漢軍也死傷四五百人,於是韓信整頓兵馬也返回大本營。當行至一山坡,忽有後軍來報,說有楚軍騎兵追來。只見遠方塵土飛揚,殺聲震天。漢軍本來已十分疲憊,這時隊伍大嘩。韓信兵馬到坡頂,見來敵不足五百騎,便急速點兵迎敵。他命令士兵3人一排,結果多出2名;接著命令士兵5人一排,結果多出3名;他又命令士兵7人一排,結果又多出2名。韓信馬上向將士們宣布:我軍有1073名勇士,敵人不足五百,我們居高臨下,以眾擊寡,一定能打敗敵人。漢軍本來就信服自己的統帥,這一來更相信韓信是“神仙下凡”、“神機妙算”。於是士氣大振。一時間旌旗搖動,鼓聲喧天,漢軍步步進逼,楚軍亂作一團。交戰不久,楚軍大敗而逃。首先我們先求3、5、7、的最低公倍數105(註:因為3、5、7為兩兩互質的整數,故其最低公倍數為這些數的積),乘以10,然後再加23,得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人 中國有一本數學古書孫子算經也有類似的問題:今有物,不知其數,三三數之,剩二,五五數之,剩三,七七數之,剩二,問物幾何? 答曰:二十三 術曰:三三數之剩二,置一百四十,五五數之剩三,置六十三,七七數之剩二,置三十,並之,得二百三十三,以二百一十減之,即得。凡三三數之剩一,則置七十,五五數之剩一,則置二十一,七七數之剩一,則置十五,即得。 孫子算經的作者及確實著作年代均不可考,不過根據考證,著作年代不會在晉朝之後,以這個考證來說上面這種問題的解法,中國人發現得比西方早,所以這個問題的推廣及其解法,被稱為中國剩餘定理。中國剩餘定理(Chinese Remainder Theorem)在近代抽象代數學中占有一席非常重要的地位。
秦九韶算法把一個n次多項式f(x)=a[n]x^n+a[n-1]x^(n-1)+......+a[1]x+a[0]改寫成如下形式: f(x)=a[n]x^n+a[n-1]x^(n-1))+......+a[1]x+a[0] =(a[n]x^(n-1)+a[n-1]x^(n-2)+......+a[1])x+a[0] =((a[n]x^(n-2)+a[n-1]x^(n-3)+......+a[2])x+a[1])x+a[0] =...... =(......((a[n]x+a[n-1])x+a[n-2])x+......+a[1])x+a[0]. 求多項式的值時,首先計算最內層括弧內一次多項式的值,即 v[1]=a[n]x+a[n-1] 然後由內向外逐層計算一次多項式的值,即 v[2]=v[1]x+a[n-2] v[3]=v[2]x+a[n-3] ...... v[n]=v[n-1]x+a[0] 這樣,求n次多項式f(x)的值就轉化為求n個一次多項式的值。 (註:中括弧里的數表示下標) 上述方法稱為秦九韶算法。直到今天,這種算法仍是多項式求值比較先進的算法 該算法看似簡單,其最大的意義在於將求n次多項式的值轉化為求n個一次多項式的值。在人工計算時,利用秦九韶算法和其中的係數表可以大幅簡化運算;對於電腦程式算法而言,加法比乘法的計算效率要高很多,因此該算法仍有極大的意義,用於減少CPU運算時間。
外國人對秦九韶的評價秦九韶是他那個民族,他那個時代,並且確實也是所有時代最偉大的數學家之一。 --------------美國科學史家 薩頓
生活中的秦九韶對於秦九韶究竟是何等樣人,除了“偉大的數學家”之外,通常就諱莫如深了。用現代的眼光看,秦九韶可能是中國歷史上少見的奇人之一。關於秦九韶究竟是何等樣人,其實宋人文獻中留下了相當豐富的記載,主要可見於周密(人名)的《癸辛雜識續集》卷下和著名詞人劉克莊文集中的“繳秦九韶知臨江軍奏狀”。秦九韶18歲就統帥私人武裝,為人“豪宕不羈”,如果將他和義大利文藝復興時期的那些風雲人物相比,竟有幾分相似:他多才多藝,懂得星占、數學、音樂、建築,還擅長詩文,會騎術、劍術、踢球等等。同時又利慾薰心,驕奢淫逸,熱衷於做官,一心往上爬。秦九韶做過幾任地方官,最後死在梅州任上。他最高做到大約相當於今天局級的官職。 秦九韶行為乖戾,出人意表,被他的同時代人認為是“不孝、不義、不仁、不廉”,平日橫行鄉里,惡霸一方,所以多次被褫去官職或取消任命。例如,在他擔任地方長官的父親宴客時,他帶著妓女出席。又如,他竟能將他上司的田產“以術攫取之”,在其中建造他的超豪華莊園(他親自設計那些奇特的房屋)。再如,他命令手下殺死自己的兒子,而且親自設計了毒死、用劍自裁、溺死三種方案;當得知這名手下偷偷放了他兒子時,他竟巨額懸賞,滿世界追殺兒子和這名手下。有一年夏天,秦九韶和一個他所寵愛的姬妾月夜在庭院中交歡,不意被一個汲水的僕役撞見,他認為那僕役有意窺探他的隱私,就誣告該僕役偷盜,將其送官,要求判僕役黥面流放。地方官認為該僕役罪不至此,沒有按照秦九韶的要求判決,秦九韶為此懷恨地方官,竟企圖將他毒死。當時的記載說秦九韶“多蓄毒藥,如所不喜者,必遭其毒手”。這就是被劉克莊稱為“暴如虎狼,毒如蛇蠍,非復人類”的秦九韶。毫無疑問,他是一個瘋狂的惡棍,但與此同時,他確實也是一個天才的數學家。我們甚至可以推想,如果他有時間或精力寫下音樂或建築方面的著作,也可能又有某項歷史性的貢獻。