標籤:方法

大衍求一術
大衍求一術

1作者簡介

南宋,數學家秦九韶(公元1202~1261年)在1247年(淳祐七年)著成『數書九章』十八卷.全書共81道題,分為九大類:大衍類、天時類、田域類、測望類、賦役類、錢穀類、營建類、軍旅類、市易類。這是一部劃時代的巨著,它總結了前人在開方中所使用的列籌方法,將其整齊而有系統地應用到高次方程的有理或無理根的求解上去,其中對「大衍求一術」[一次同餘組解法)和「正負開方術」[高次方程的數值解法)等有十分深入的研究。其中的」大衍求一術」[一次同餘組解法),在世界數學史上佔有崇高的地位。在古代中載有」物不知數」這個問題,舉例說明:有一數,三三數之餘二,五五數之餘三,七七數之餘二,問此數為何?這一類問題的解法可以推廣成解一次同餘式組的一般方法.奏九韶給出了理論上的證明,並將它定名為」大衍求一術」。

2主要內容

中國古代求解一類大衍問題的方法。大衍問題源於《孫子算經》中的「物不知數」問題:「今有物,不知其數,三三數之剩二,五五數之剩三,七七數之剩二,問物幾何?」這是屬於現代數論中求解一次同餘式方程組問題。宋代數學家秦九韶在《數書九章》(1247年成書)中對此類問題的解法作了系統的論述,並稱之為大衍求一術。德國數學家C.F.高斯是在1801年才建立起同餘理論的,大衍求一術反映了中國古代數學的高度成就。

3大衍求一術與中國剩餘定理

在中國古代勞動人民中,長期流傳著「隔牆算」、「剪管術」、「秦王暗點兵」等數學遊戲。有一首「孫子歌」①,甚至遠渡重洋,輸入日本:
「三人同行七十稀,五樹梅花廿一枝,
七子團圓正半月,除百零五便得知。」
這些饒有趣味的數學遊戲,以各種不同形式,介紹世界聞名的「孫子問題」的解法,通俗地反映了中國古代數學一項卓越的成就。
「孫子問題」在現代數論中是一個一次同餘問題,它最早出現在中國公元四世紀的數學著作《孫子算經》中。《孫子算經》卷下「物不知數」題說:有物不知其數,三個一數餘二,五個一數餘三,七個一數又餘二,問該物總數幾何?顯然,這相當於求不定方程組
N=3x+2,N=5y+3,N=7z+2
的正整數解N,或用現代數論符號表示,等價於解下列的一次同餘組:
N 2(mod3) 3(mod5) 2(mod7)②
《孫子算經》所給答案是N=23。由於孫子問題數據比較簡單,這個答數通過試算也可以得到。但是《孫子算經》並不是這樣做的。「物不知數」題的術文指出解題的方法:三三數之,取數七十,與餘數二相乘;五五數之,取數二十一,與餘數三相乘;七七數之,取數十五,與餘數二相乘。將諸乘積相加,然後減去一百零五的倍數。列成算式就是:
N=70×2+21×3+15×2-2×105。
這裡105是模數3、5、7的最小公倍數,容易看出,《孫子算經》給出的是符合條件的最小正整數。對於一般餘數的情形,《孫子算經》術文指出,只要把上述演算法中的餘數2、3、2分別換成新的餘數就行了。以R1、R2、R3表示這些餘數,那麼《孫子算經》相當於給出公式
N=70×R1+21×R2+15×R3-P×105(p是整數)。
孫子演算法的關鍵,在於70、21和15這三個數的確定。後來流傳的《孫子歌》中所說「七十稀」、「廿一枝」和「正半月」,就是暗指這三個關鍵的數字。《孫子算經》沒有說明這三個數的來歷。實際上,它們具有如下特性:
也就是說,這三個數可以從最小公倍數M=3×5×7=105中各約去模數3、5、7后,再分別乘以整數2、1、1而得到。假令k1=2,K2=1,K3=1,那麼整數Ki(i=1,2,3)的選取使所得到的三數70、21、15被相應模數相除的時候餘數都是1。由此出發,立即可以推出,在餘數是R1、R2、R3的情況下,
綜合以上三式又可得到
因為M=3×5×7可被它的任一因子整除,於是又有:
這裡P是整數。這就證明了《孫子算經》的公式。應用上述推理,可以完全類似地把孫子演算法推廣到一般情形:設有一數N,分別被兩兩互素的幾個數a1、a2、……an相除得餘數R1、R2、……Rn,即
N≡Ri(modai)(i=1、2、……n),
只需求出一組數Ki,使滿足
那麼適合已給一次同餘組的最小正數解是
(P是整數,M=a1×a2×……×an),這就是現代數論中著名的剩餘定理。如上所說,它的基本形式已經包含在《孫子算經》「物不知數」題的解法之中。不過《孫子算經》沒有明確地表述這個一般的定理。
孫子問題出現在公元四世紀的中國算書中,這並不是偶然的。中國古代天文曆法資料表明,一次同餘問題的研究,明顯地受到天文、曆法需要的推動,特別是和古代曆法中所謂「上元積年」的計算密切相關。大家知道,一部曆法,需要規定一個起算時間,中國古代歷算家把這個起點叫做「曆元」或「上元」,並且把從曆元到編歷年所累積的時間叫做「上元積年」。上元積年的推算需要求解一組一次同餘式。以公元三世紀三國時期魏國施行的《景初歷》做例,這部曆法規定以冬至、朔旦(朔日子夜)和甲子日零時會合的時刻作為曆元。設a是一回歸年日數,b是一朔望月日數,當年冬至距甲子日零時是R1日,離平朔時刻是R2日,那麼《景初歷》上元積元數N就是同餘組
aN≡Ri(mod60)≡R2(mdb)
的解①。到了南北朝時期,祖沖之《大明曆》(公元462年)更要求曆元必須同時是甲子年的開始,而且「日月合壁」、「五星聯珠」(就是日、月、五大行星處在同一方位),月亮又恰好行經它的近地點和升交點。這樣的條件下推算上元積年,就相當於要求解十個同餘式了。天文曆法數據一般又都十分龐雜,所以,在《孫子算經》成書前後的魏晉南北朝時期,中國的天文歷算家無疑已經能夠求解形式比《孫子算經》「物不知數」題複雜得多的一次同餘式,因而必定掌握了按一定程序計算一次同餘式的方法①。《孫子算經》比例題的形式總結、反映了這一事實。以後天文歷算家長期沿用孫子演算法推算上元積年,這中間肯定會引起更加深入的探討。到公元十三世紀,大數學家秦九韶集前法之大成,終於在一次同餘式的研究上獲得了超越前人的輝煌成果。
秦九韶,字道古,生活於南宋時期,自幼喜好數學,經過長期積累和苦心鑽研,於公元1247年寫成《數書九章》。這部中世紀的數學傑作,在許多方面都有創造,其中求解一次同餘組的「大衍求一術」和求高次方程數值解的「正負開方術」,更是具有世界意義的成就。
這裡主要介紹秦九韶對一次同餘論的偉大貢獻。
秦九韶在《數書九章》中明確地系統地敘述了求解一次同餘組的一般計算步驟。秦的方法,正是前述的剩餘定理。我們知道,剩餘定理把一般的一
的一組數Ki的選定。秦九韶給這些數起名叫「乘率」,並且在《數書九章》卷一「大衍總術」中詳載了計算乘率的方法——「大衍求一術」。
為了介紹「大衍求一術」,我們以任一乘率ki的計算作例。如果Gi=
Gi≡gi(modai),
於是kiGi≡Kigi(modai),
但是因為kiGi≡1(modai),
所以問題歸結為求ki使適合kigi≡1(modai)。秦九韶把ai叫「定數」,gi叫「奇數」,他的「大衍求一術」,用現代語言解釋,實際就是把奇數gi和定數ai輾轉相除,相繼得商數q1、q2、……qn和餘數r1、r2、……rn,在輾轉相除的時候,隨即算出下面右列的c值:
秦九韶指出,當rn=1而n是偶數的時候,最後得到的cn就是所求乘率ki。如果r1=1而n是奇數,那麼把rn-1和rn相除,形式上令qn+1=rn-1-1,那麼餘數rn+1仍舊是1,再作cn+1=qn+1Cn+Cn-1,這時n+1是偶數,cn+1就是所求的ki。不論哪種情形,最後一步都出現餘數1,整個計算到此終止,秦九韶因此把他的方法叫做「求一術」(至於「大衍」的意思,秦九韶本人在《數書九章》序中把它和《周易》「大衍之數」相附會)。可以證明,秦九韶這一演算法是完全正確,十分嚴密的式。
在秦九韶那個時代,計算仍然使用算籌。秦九韶在一個小方盤上,右上布置奇數g,右下布置定數a,左上置1(他叫它做「天元1」),然後在右行上下交互以少除多,所得商數和左上(或下)相乘併入左下(或上),直到右上方出現1為止。下頁就是秦九韶的一般籌算圖式,右邊是一個數字例子(g=20,a=27,K= c4=23)。
秦九韶在《數書九章》中採集了大量例題,如「古歷會積」、「積尺尋源」、「推計土功」、「程行計地」等等,廣泛應用大衍求一術來解決曆法、工程、賦役和軍旅等實際問題。在這些實際問題中,模數ai並不總是兩兩互素的整數。秦九韶區分了「元數」(ai是整數)、「收數」(ai是小數)、「通數」(ai是分數)等不同情形,並且對每種情形給出了處理方法。「大衍總術」把「收數」和「通數」化成「元數」的情形來計算,而對於元數不兩兩互素的情形,給出了可靠的程序,適當選取那些元數的因子作定數而把問題歸結為兩兩互素的情形①。所有這些系統的理論,周密的考慮,即使以今天的眼光看來也很不簡單,充分顯示了秦九韶高超的數學水平和計算技巧。
秦九韶小時曾跟隨他父親到南宋京城杭州,向太史局(主管天文曆法的機構)的官員學習天文曆法,「大衍求一術」很可能就是他總結天文曆法計算上元積年方法的結果。但是「大衍求一術」似乎沒有為他同時代的人所充分理解。明中葉以後幾乎失傳。一直到清代,「大衍求一術」又重新被發掘出來,引起了許多學者(張敦仁、李銳、駱騰鳳、黃宗憲等)的興趣。他們對「大衍求一術」進行了解釋、改進和簡化,其中黃宗憲《求一術通解》對模數非兩兩互素的情形給出了更加簡明的方法,但是時代已是晚清。
從《孫子算經》「物不知數」題到秦九韶的「大衍求一術」,中國古代數學家對一次同餘式的研究,不僅在中國數學史上而且在世界數學史上佔有光榮的地位。在歐洲,最早接觸一次同餘式的,是和秦九韶同時代的義大利數學家裴波那契(1170—1250),他在《演算法之書》中給出了兩個一次同餘問題,但是沒有一般的演算法。這兩個問題從形式到數據都和孫子物不知數題相仿,整個水平沒有超過《孫子算經》。直到十八、十九世紀,大數學家歐拉(1707—1783)於公元1743年、高斯(1777—1855)於公元1801年對一般一次同餘式進行了詳細研究,才重新獲得和秦九韶「大衍求一術」相同的定理,並且對模數兩兩互素的情形給出了嚴格證明。歐拉和高斯事先並不知道中國人的工作。公元1852年英國傳教士偉烈亞力(1815—1887)發表《中國科學摘記》,介紹了《孫子算經》物不知數題和秦九韶的解法,引起了歐洲學者的重視。1876年,德國馬蒂生(1830—1906)首先指出孫子問題的解法和高斯方法一致,當時德國著名數學史家康托(1829—1920)看到馬蒂生的文章以後,高度評價了「大衍術」,並且稱讚發現這一方法的中國數學家是「最幸運的天才」。直到今天,「大衍求一術」仍然引起西方數學史家濃厚的研究興趣。如1973年,美國出版的一部數學史專著《十三世紀的中國數學》中,系統介紹了中國學者在一次同餘論方面的成就,作者力勃雷希(比利時人)在評論秦九韶的貢獻的時候說道:「秦九韶在不定分析方面的著作時代頗早,考慮到這一點,我們就會看到,薩頓②稱秦九韶為『他那個民族、他那個時代、並且確實也是所有時代最偉大的數學家之一』,是毫不誇張的。」
印度學者對一次同餘論也有過重要貢獻。從公元六世紀到十二世紀,他們發展了一種稱為「庫塔卡」的演算法,用來求解和一次同餘式等價的不定方程組。「庫塔卡」法出現在孫子演算法之後,印度數學家婆羅門笈多(七世紀)、摩柯吠羅(九世紀)等人的著作中,都有和物不知數題相同的一次同餘問題。這當然不是要藉此斷言「庫塔卡」法一定受到了孫子演算法的影響,但是有人(如萬海依等)硬說中國的「大衍求一術」來源於「庫塔卡」,就是毫無根據的妄說了。萬海依居然把中國演算法中數碼從左到右橫寫作為「大衍術」受印度影響的重要根據。大家知道,中國古代至遲從春秋戰國時期就開始使用算籌記數,我們今天還可以從現存的公元前三世紀的貨幣上看到這種從左到右的記數方法。由此可見,萬海依的論點多麼荒唐可笑。中國古代數學家對一次同餘論的研究有明顯的獨創性和繼承性,「大衍求一術」在世界數學史上的崇高地位是毋容置疑的,正因為這樣,在西方數學史著作中,一直公正地稱求解一次同餘組的剩餘定理為「中國剩餘定理」。
--------------------------------------------------------------------------------
① 「孫子歌」又名「韓信點兵」,載於明程大位《演算法統宗》(公元1592年),但是實際上在這以前早已流傳民間。
① 按曆元的定義,從曆元到當年冬至,恰好經過N個回歸年,合a×N日。甲子紀日,以甲子為首60日一周期,所以60除aN,餘數應該是當年冬至離最近一個甲子日的日數,這就得到同餘式aN≡R1(mod60)。按同樣道理可以得出第二個同餘式。
① 積年的方法,原來開始於漢代。但是由於漢代天文曆法家利用了當時天文觀測的特殊數據,他們推算上元積年,只要解一二個數據不太複雜的一次同餘式。例如可以驗證,《三統曆》(公元前一世紀)的上元積年滿足形如145×4617×p≡135(mod 1728)(P是整數,積年數x=4617×p)
式 。這樣的同餘式是通過試算就可以得到答案的。從公元三世紀開始,隨著天文測量技術的提高,對曆法提出更精密的要求來,這時推算上元積年的同餘式越來越複雜,這就促使當時的天文歷算家去尋求一次同餘式的一般計算方法。
① 事實上,設l2=q2,L3=q3L2+1,L4=q4L3+L2,……Ln=qnln-1+ln-2,那麼r1=ai-giq1=ai-c1gi, r2=gi-r1q2=gi-(ai-c1gi)q2=c2g4-l2a4,r3=r1-r2g4=(ai-c1gi)-(c2gi-l2ai)q3=l3ai-c3gi,…………當rn=1並且n是偶數的時候(根據正文所說,總可以把n是奇數情形化作偶數情形來處理),顯然有rn-1=lI-1;rn=cngi-liai=1,就是cngi(modai)。這就證明了Cn就是所求的K3。
② 秦九韶採用的方法是在那些元數ai中約去適當的公因子,從而對每個元數求得一個因子ti,使得m=t1×t2×……×tn是那些ai的最小公倍數,而且各個ti兩兩互素,然後以這些ti為定數,按大衍求一術計算相應的ki。
上一篇[AOC 917Vw]    下一篇 [AOC 416V]

相關評論

同義詞:暫無同義詞