呂 鵬 紀(jì)志剛

(上海交通大學(xué)科學(xué)史與科學(xué)文化研究院，上海 200240)

數(shù)學(xué)史家對(duì)庫(kù)塔卡算法的興趣還在于其與中算不定問(wèn)題解法的比較上。19世紀(jì)傳教士偉烈亞力(A. Wylie)在《北華捷報(bào)》上撰文將秦九韶的“大衍術(shù)”(2)西方學(xué)者似乎并不特別區(qū)分大衍求一術(shù)和大衍總數(shù)術(shù)，而習(xí)慣統(tǒng)稱為大衍術(shù)(Ta-yen Rule)。介紹給西方，他可能還是第一個(gè)將印度庫(kù)塔卡和中算大衍術(shù)聯(lián)系在一起的人。(3)偉烈亞力寫(xiě)道：“(大衍術(shù))所表現(xiàn)的式子，或是與之類似的東西，在印度人那里被稱作為‘庫(kù)塔卡’(Cuttaca)。這個(gè)詞可以被譯為‘pulverizer’，意為無(wú)限的乘法，并且和‘大衍’的意思相差不遠(yuǎn)。此過(guò)程連同結(jié)果在印度數(shù)學(xué)中得到發(fā)現(xiàn)，在歐洲不僅吸引了廣泛的關(guān)注，還在科學(xué)史研究中引起了一些奇特的猜測(cè)”(《北華捷報(bào)》1852年10月23號(hào))。[6]沈康身仔細(xì)考察了庫(kù)塔卡與大衍求一術(shù)的關(guān)系，指出兩者在數(shù)學(xué)意義、問(wèn)題情景和輾轉(zhuǎn)相除方法上的相似性，并用了“平行性”一詞來(lái)描述這種相似性。[7]李倍始(U. Libbrecht)在這個(gè)問(wèn)題上也做過(guò)專門的研究，指出庫(kù)塔卡本質(zhì)是一種迭代解法，不同于大衍術(shù)使用的連分?jǐn)?shù)解法，所以兩者毫無(wú)聯(lián)系([8]，365～366頁(yè))。他的比較只依賴現(xiàn)代數(shù)學(xué)分析，與庫(kù)塔卡或大衍術(shù)原貌都相距甚遠(yuǎn)。并且，無(wú)論是沈康身還是李倍始都沒(méi)有提及用庫(kù)塔卡解含三個(gè)及以上模數(shù)的同余式組的情形，而這樣的同余式組正是大衍總數(shù)術(shù)的主要處理對(duì)象。因此，他們的比較工作是不充分的。本論文將就這點(diǎn)展現(xiàn)兩種方法的實(shí)際計(jì)算過(guò)程，以求說(shuō)明清楚庫(kù)塔卡和大衍求一術(shù)，以及和大衍總數(shù)術(shù)之間確切的異同之處。

1 庫(kù)塔卡算法詳解

庫(kù)塔卡問(wèn)題的代數(shù)表達(dá)式為：

N≡R1(moda)≡R2(modb)，(*1)，

它可化為二元一次不定方程形式

N=ax+R1=by+R2, (0≤R1

若R1-R2=c，則上式可變形為

庫(kù)塔卡是古代印度數(shù)學(xué)家們的重點(diǎn)研究對(duì)象。這是因?yàn)樗c天文計(jì)算密切相關(guān)。比如，已知在一紀(jì)(yuga，意為“會(huì)合”)周期的D日間某行星在天球上的周轉(zhuǎn)圈數(shù)為R，從紀(jì)元起經(jīng)過(guò)天數(shù)y時(shí)行星周轉(zhuǎn)整圈數(shù)為x，并且周轉(zhuǎn)不足一圈之余數(shù)為行星的黃經(jīng)λ，那么根據(jù)比例關(guān)系就能得到不定關(guān)系式：

式子中的紀(jì)元常數(shù)R和D通常都是非常巨大的數(shù)，因而這里需要使用庫(kù)塔卡算法來(lái)把x和y計(jì)算出來(lái)，其中y是一個(gè)以日數(shù)為單位的量，是為“上元積日”([9]，185～186頁(yè))。類似的方法可以推廣到求兩個(gè)或更多行星的會(huì)合周期，如《婆羅摩修正體系》(以下簡(jiǎn)稱《體系》)第18章6偈所說(shuō)：“兩個(gè)[行星]的會(huì)合周期即為兩個(gè)除數(shù)的積；會(huì)合點(diǎn)的推移就是這兩者的原余數(shù)。因此，用庫(kù)塔卡算法就可以計(jì)算出三個(gè)或更多行星的會(huì)合周期”([1]，326頁(yè)；[10]，442頁(yè))，其具體做法將在后面說(shuō)明。

1.1 阿耶波多-婆什迦羅一世的解法

首先看《阿耶波多歷算書(shū)》是怎樣來(lái)解“伴有余數(shù)的庫(kù)塔卡拉”問(wèn)題的。其第2章32～33兩偈經(jīng)文如下：

若僅加入最少量的解釋性語(yǔ)句(方括號(hào)內(nèi))，我們將上述經(jīng)文直譯為：

(33：)下面的乘上上面的，并加入最后的。當(dāng)除以有較小余數(shù)的除數(shù)時(shí)，余數(shù)乘上有較大余數(shù)的除數(shù)，再加上較大的余數(shù)，就得到被兩個(gè)除數(shù)[除后有那些]余數(shù)[的數(shù)]。

從這段的經(jīng)文中我們很難總結(jié)出一個(gè)完整的算法。也許阿耶波多的目的僅是希望弟子們通過(guò)吟誦這條經(jīng)文來(lái)記下算法中的一些關(guān)鍵點(diǎn)。因此，為確切地理解其含義，我們求助于婆什迦羅一世的《注釋》([11]，132～133頁(yè))。除去純梵語(yǔ)語(yǔ)法方面的解釋之外，我們將他對(duì)經(jīng)文的注釋翻譯如下：

(32：)所謂“需用有較小余數(shù)的除數(shù)去除有較大余數(shù)的除數(shù)”，就是說(shuō)對(duì)于某個(gè)除數(shù)來(lái)說(shuō)，它產(chǎn)生出較大的余數(shù)，因此它便被稱作為“有較大余數(shù)的除數(shù)”。并且這個(gè)有較大余數(shù)的除數(shù)需要被[一個(gè)數(shù)]來(lái)除。被什么[除]？被“有較小余數(shù)的除數(shù)”[來(lái)除]。所謂“[取]余數(shù)輾轉(zhuǎn)相除”，就是說(shuō)所得到的商沒(méi)有用處，用余數(shù)來(lái)進(jìn)行運(yùn)算。用余數(shù)再互除便是“[取]余數(shù)輾轉(zhuǎn)相除”的意思。所謂“乘上聰明數(shù)”，就是乘上靠自己的智慧[得到的數(shù)]的意思。那么，如何做才叫是乘上靠自己的智慧[得到的數(shù)]呢？這里的這個(gè)量乘上這個(gè)數(shù)，再加上或減去余數(shù)間的差后，可以得到[一個(gè)數(shù)]能整除這個(gè)量。所謂“加入余數(shù)間的差”，就是說(shuō)偶數(shù)時(shí)加，奇數(shù)時(shí)減。這是根據(jù)相傳不斷[的傳統(tǒng)]解釋的。如此輾轉(zhuǎn)相除，將商像足跡一樣排列，聰明數(shù)放下面，然后最后得到的商放在聰明數(shù)的下面。

(33：)所謂“下面的乘上上面的”，[就是說(shuō)]上面的量要用放在下面的量去乘?！安⒓尤胱詈蟮摹保钦f(shuō)加上最后的量，即最后得到的商。反反復(fù)復(fù)執(zhí)行這樣的運(yùn)算，直到運(yùn)算全部結(jié)束。所謂“當(dāng)除以有較小余數(shù)的除數(shù)時(shí)，余數(shù)”，[就是說(shuō)]用那個(gè)有較小余數(shù)的除數(shù)除時(shí)[所得到的]余數(shù)，即取那個(gè)有較小余數(shù)的除數(shù)和之前運(yùn)算所計(jì)算出來(lái)的量相除后得到的余數(shù)。所謂“乘上有較大余數(shù)的除數(shù)”，[就是說(shuō)]用有較大余數(shù)的除數(shù)乘。所謂“兩除數(shù)的余數(shù)”，[就是]從兩個(gè)除數(shù)得到的余數(shù)，余數(shù)就是[那些所給的]數(shù)字。所謂“加上較大的余數(shù)”，就是說(shuō)[之前的結(jié)果]要加上較大的余數(shù)。這里的[兩句]的意思是：用有較小余數(shù)的除數(shù)除時(shí)所得到的余數(shù)乘上有較大余數(shù)的除數(shù)，再加上較大的余數(shù)，其結(jié)果就是被兩除數(shù)除的那個(gè)量。以上便解釋了伴有余數(shù)的庫(kù)塔卡。

緊接著文字注釋，婆什迦羅又輔以多道例題來(lái)進(jìn)一步演示庫(kù)塔卡的解法。如其第2題為：

[一個(gè)量如果除以]十二得到的余數(shù)是五，另外還知道這個(gè)量被三十一除之后[得到]的余數(shù)是七。這個(gè)量是多少？

這是要求同余式組N≡ 5 (mod 12) ≡ 7 (mod 31)中N的值。這里，阿耶波多經(jīng)文中的“兩個(gè)除數(shù)”便是指12和31，余數(shù)則分別為5和17。因此，12又被稱為“有較小余數(shù)的除數(shù)”，31則為“有較大余數(shù)的除數(shù)”，“余數(shù)間的差”是7-5=2。基于經(jīng)文和注釋，庫(kù)塔卡求解過(guò)程具體演示如下。

(i)“需用有較小余數(shù)的除數(shù)去除有較大余數(shù)的除數(shù)”

即是取31作為被除數(shù)，12為除數(shù)，做除法：

31 ÷ 12=2……7。

由于說(shuō)第一次“所得到的商沒(méi)有用處”，我們舍去2，取余數(shù)7進(jìn)入下一步。

(ii)“[取]余數(shù)輾轉(zhuǎn)相除”

即取前一步的除數(shù)12作為被除數(shù)，余數(shù)7為除數(shù)，再做除法。然后不斷重復(fù)這一過(guò)程：

12 ÷ 7=1……5，7 ÷ 5=1……2。

由于此時(shí)數(shù)字已足夠簡(jiǎn)單，停止除法。這步總共得到2個(gè)商，并且最后剩下的余數(shù)為2。

(iii)“乘上聰明數(shù)后加入余數(shù)間的差”

即通過(guò)試商找出一數(shù)m，使得它與最后的余數(shù)2的乘積加上原來(lái)余數(shù)間的差2后可以被最后除法的除數(shù)5整除：

(2 ×m+2) ÷ 5=整數(shù)。

略加觀察可以發(fā)現(xiàn)m=4。由于m=4是被試商發(fā)現(xiàn)的，因此它被稱為“聰明數(shù)”。最后的商為

(2 × 4+2) ÷ 5=2。

(iv)“將商像足跡一樣排列，聰明數(shù)放下面，然后最后得到的商放在聰明數(shù)的下面”

即將除第一次以外的商從上到下排列，之后放入聰明數(shù)和最后的商，它們好似一串足跡：

1142

對(duì)于這串?dāng)?shù)字列，婆什迦羅二世及一些注釋者也稱之為“商的葉蔓”(phala-vallī)。

(v)“下面的乘上上面的，并加入最后的”

經(jīng)文中這句話最為費(fèi)解，而婆什迦羅一世的注釋也不十分明了。為此我們參考同時(shí)代婆羅摩笈多的規(guī)則([10]，441～442頁(yè))，發(fā)現(xiàn)所謂“下面的”是指數(shù)字列中的倒數(shù)第二項(xiàng)4，“上面的”是其上面的倒數(shù)第三項(xiàng)1，“最后的”就是指最后一項(xiàng)2。因此，這步的運(yùn)算就是：

4 × 1+2=6。

之后，還需要將結(jié)果替換掉原來(lái)數(shù)字列的倒數(shù)第三項(xiàng)，并消去最后一項(xiàng)，得到：

164

(vi)“反反復(fù)復(fù)執(zhí)行這樣的運(yùn)算，直到運(yùn)算全部結(jié)束”

重復(fù)(v)的步驟，執(zhí)行運(yùn)算：

6× 1+4=10。

此后，數(shù)字列變?yōu)椋?/p>

106

由于數(shù)字列只剩下兩項(xiàng)，(v)的運(yùn)算停止。

(vii)“用有較小的余數(shù)的除數(shù)除時(shí)所得到的余數(shù)乘上有較大余數(shù)的除數(shù)，再加上較大的余數(shù)”

取上一步的最后結(jié)果10，除以原題中“有較小余數(shù)的除數(shù)”12，得商0、余數(shù)10。余數(shù)再乘上“有較大余數(shù)的除數(shù)”31，再加上那個(gè)較大的余數(shù)7，結(jié)果為317。它便是所求的數(shù)N。即：

10 ÷ 12=0……10，N=10 × 31+7=317。

以上是“伴有余數(shù)的庫(kù)塔卡”的解法，所針對(duì)的問(wèn)題是含有兩個(gè)模數(shù)的同余式組(*1)。對(duì)于“不伴有余數(shù)的庫(kù)塔卡”或“固定庫(kù)塔卡”，上面的解法同樣適用，只要將不定方程(*2)中x的“乘數(shù)”a看作是“有較大余數(shù)的除數(shù)”，“除數(shù)”b為“有較小余數(shù)的除數(shù)”(其余數(shù)為0)，“付數(shù)”c則是“余數(shù)間的差”。

此外，對(duì)于上面的算法還有兩點(diǎn)需要說(shuō)明。一點(diǎn)是，針對(duì)阿耶波多第(iii)步求聰明數(shù)時(shí)要求“加入”余數(shù)間的差，對(duì)此婆什迦羅一世的注釋卻是“加上或者減去”，并且說(shuō)“偶數(shù)時(shí)加，奇數(shù)時(shí)減”。這里的偶數(shù)或是奇數(shù)指的其實(shí)是互除環(huán)節(jié)結(jié)束后第(iv)步數(shù)字列中的數(shù)字的個(gè)數(shù)。婆羅摩笈多的庫(kù)塔卡規(guī)則對(duì)此表示得更加明確，整個(gè)互除環(huán)節(jié)時(shí)若所得的商數(shù)為奇數(shù)個(gè)時(shí)，付數(shù)的性質(zhì)(符號(hào))不變；偶數(shù)個(gè)時(shí)則相反([1]，332～333頁(yè))。

另一點(diǎn)是，關(guān)于第(vii)步“用有較小的余數(shù)的除數(shù)除時(shí)所得到的余數(shù)……”計(jì)算的意義。根據(jù)下節(jié)的算法演示可以知道，最后數(shù)字列的最上面的那個(gè)數(shù)其實(shí)是同余式的不定方程形式中的x的解。將它除以“有較小余數(shù)的除數(shù)”后所得的余數(shù)就是方程的最小解。與此相關(guān)，有些印度數(shù)學(xué)家，如普利突大卡、婆什迦羅二世等在解不定方程形式(*2)的庫(kù)塔卡問(wèn)題時(shí)，通常還會(huì)保留第一次除法的商。這樣迭代計(jì)算后最上面的那個(gè)數(shù)就變成了不定方程中y的解。

1.2 庫(kù)塔卡算法的一般步驟及其證明

由于庫(kù)塔卡問(wèn)題可以有同余式組表示(*1)和不定方程表示(*2)，下面我們就用后者

來(lái)演示庫(kù)塔卡算法的一般運(yùn)算程序，其目的是求“乘數(shù)”x。首先做除法a÷b，得到第一次的商q1余數(shù)r1，然后取之前的除數(shù)和余數(shù)再做除法b÷r1，得到第二次的商q2余數(shù)r2。這樣反復(fù)取前一次的除數(shù)與余數(shù)互除，得到一連串的商和余數(shù)：

r1÷r2=q3……r3，

r2÷r3=q4……r4，

…

rn-1÷rn=qn+1……rn+1(使得rn+1足夠小)。

除第一次得到的商數(shù)q1以外，將商排列如下：

q2q3q4?qn+1

將m和l也放在剛才的商的數(shù)字列下面，就有：

q2q3q4?qn+1ml

這之后，將其中倒數(shù)第二項(xiàng)乘以倒數(shù)第三項(xiàng)，積加上倒數(shù)第一項(xiàng)，所得的和取代原來(lái)倒數(shù)第三項(xiàng)，并消去最后一項(xiàng)：

q2?qi-2qi-1qi

→

q2?q=i=-=2=qi-2qi-1+qiqi-1q=i=

→

q2?qi-2qi-1+qiqi-1

對(duì)新數(shù)字列重復(fù)剛才的運(yùn)算，直到數(shù)字列中只剩下兩個(gè)數(shù)字。此時(shí)最上面的數(shù)字就是原不定方程中x的一個(gè)解α。若a=bt+a0(t=0，1，…)，則得到最小解α0；將之代入原不定方程，可以得到y(tǒng)的最小解β0。

下面是對(duì)庫(kù)塔卡算法的一般證明。(6)此處的證明綜合了矢野道雄(1980)和Keller(2006)的工作。首先通過(guò)互除環(huán)節(jié)得到的商(q1，q2，…，q2p，q2p+1)和余數(shù)(r1，r2，…，r2p，r2p+1)，可以獲得如下一系列的不定方程：

?

接下來(lái)，根據(jù)得到的商(q2，…，q2p，q2p+1)的個(gè)數(shù)的奇偶，解最后得到的關(guān)于xp或yp+1的不定方程。由于系數(shù)已化簡(jiǎn)，容易通過(guò)觀察發(fā)現(xiàn)(yp，xp)或(xp，yp+1)的一組解，其中yp或xp的值稱為聰明數(shù)m，對(duì)應(yīng)的商數(shù)xp或yp+1是最后的商l。將它們連同商(q2，…，q2p，q2p+1)排成一列后，進(jìn)入迭代運(yùn)算環(huán)節(jié)，其本質(zhì)是將最后的不定方程的一組解代入前一步的不定方程里。如此反復(fù)地代入計(jì)算，所得的最終結(jié)果就是原不定方程中x的一個(gè)解。以數(shù)字列中的商為偶數(shù)個(gè)時(shí)為例，我們用圖示來(lái)說(shuō)明這個(gè)迭代過(guò)程：

q2q3?q2pq2p+1m=xpl=yp+1

→

q2q3?q2pq2p+1xp+yp+1=ypxp

→

q2q3?q2pyp+xp=xp-1yp

→…

q2q3q4y2+x2=x1y2

→

q2q3x1+y2=y1x1

→

q2y1+x1=xy1

1.3 含三個(gè)及以上模數(shù)的同余式組的解法

上面1.1節(jié)的庫(kù)塔卡例題涉及到的是已知某數(shù)分別除以兩個(gè)除數(shù)得到相應(yīng)余數(shù)時(shí)如何來(lái)求這個(gè)數(shù)。當(dāng)除數(shù)(即同余式組中的模數(shù))有三個(gè)或三個(gè)以上時(shí)，仍可用庫(kù)塔卡來(lái)解，正如前面所引婆羅摩笈多的話：“可以計(jì)算出三個(gè)或更多行星的會(huì)合周期”。至于具體如何操作，我們?cè)绽淮罂ㄔ谧⑨尅扼w系》這部分時(shí)所提供的一道例題([1]，326頁(yè))：

什么數(shù)除以六時(shí)有余數(shù)五，除以五時(shí)有余數(shù)四，[除以]四時(shí)有余數(shù)三，[除以]三時(shí)有[余數(shù)]二？

問(wèn)題可表示成含有4個(gè)模數(shù)的一次同余式組：N≡5(mod 6)≡4(mod 5)≡3(mod 4)≡2(mod 3)，求N。特別地，這里模數(shù)并非是兩兩互素。普利突大卡所提供的解法是，先取頭兩個(gè)除數(shù)(同余式的模數(shù))6和5及它們對(duì)應(yīng)的余數(shù)來(lái)施行庫(kù)塔卡，即解同余式組N1≡5(mod 6)≡4(mod 5)。首先進(jìn)行算法第(i)(ii)步的輾轉(zhuǎn)相除：

6÷5=1……1，5÷1=5……0；

由于這里余數(shù)為0，所以(iii)中要找的聰明數(shù)m可以取任意值，這是因?yàn)椋?/p>

(0×m-1)÷1=-1。

不妨取m=1，得到(iv)的“商的蔓”，即數(shù)字列：5、1、-1。進(jìn)行一次(v)的計(jì)算后，數(shù)字列剩下兩項(xiàng)：4、1。因此，所要求的

N1=6×4+5=24+5=29。

需要注意的是，在這里的解題過(guò)程中雖然遇到了涉及0和負(fù)數(shù)的計(jì)算，但這對(duì)印度數(shù)學(xué)家們來(lái)說(shuō)不構(gòu)成絲毫的問(wèn)題。因?yàn)槠帕_摩笈多在《體系》第18章30～35偈中已給出了全套關(guān)于0和負(fù)數(shù)的計(jì)算規(guī)則([10]，442～443頁(yè))。

再回到例題，接下來(lái)普利突大卡按照婆羅摩笈多的指示，把剛才的頭兩個(gè)除數(shù)的乘積視為一新的除數(shù)，N1為相應(yīng)的余數(shù)，連同原同余式組中的第三個(gè)除數(shù)(模數(shù))和其余數(shù)再次施行庫(kù)塔卡，即解N2≡29(mod 30)≡3(mod 4)。(7)容易證明：若N≡R1(moda)≡R2(modb)，則N′≡N(moda·b)≡R1(moda)≡R2(modb)。過(guò)程如下：

30÷4=7……2，4÷2=2……0；

(0×m-26)÷2=-13→m=7。(8)這里m取7的理由是使下一步(也是最后一步)的計(jì)算結(jié)果為一個(gè)非負(fù)數(shù)。

得到“商的蔓”：7、2、-13。進(jìn)行一次(v)的計(jì)算，得到：1、2。因此

N2=30×1+29=59。

然后可以重復(fù)剛才的辦法，解N3≡59(mod 60)≡2(mod 3)。(9)有意思的是，這里普利突大卡在實(shí)際演算中并沒(méi)有單純?nèi)?0和4的乘積120作為新的模數(shù)，而是它們的最小公倍數(shù)60。其理由將在下節(jié)說(shuō)明。只不過(guò)在此之前我們發(fā)現(xiàn)N2的值59已能滿足最后“[除以]三時(shí)有[余數(shù)]二”的條件，因此計(jì)算到處結(jié)束，所求N的最小解就是59。

綜上所述，若要用庫(kù)塔卡算法解同余式組

N≡R1(moda1)≡R2(moda2)≡R3(moda3)≡…≡Rn(modan)，

可以先解出N1≡R1(moda1)≡R2(moda2)，然后再解N2≡N1(moda1a2)≡R3(moda3)。重復(fù)此過(guò)程，最后求解同余式Ni-1≡Ni-2(moda1a2…an-1)≡Rn(modan)，其解Ni-1就是要求的N。

1.4 庫(kù)塔卡算法在印度的發(fā)展與完善

針對(duì)含三個(gè)及以上模數(shù)的同余式組的方法，即婆羅摩笈多所教導(dǎo)的取“兩個(gè)除數(shù)的積”的方法，9世紀(jì)《體系》的注釋者普利突大卡還做了這樣的說(shuō)明：

此處的積應(yīng)理解為產(chǎn)生較大余數(shù)的除數(shù)與產(chǎn)生較小余數(shù)的除數(shù)除以[兩者]共同量(即最大公約數(shù))之后所得商的積([1]，327頁(yè))。(10)容易證明：若N≡R1(moda)≡R2(modb)，則N′≡N(moda·b)≡R1(moda)≡R2(modb)，L為a、b的最小公倍數(shù)。當(dāng)a、b互素時(shí)，L=ab。

開(kāi)始庫(kù)塔卡之前，若可能的話須將被除數(shù)、除數(shù)和付數(shù)約去一共同之?dāng)?shù)([12]，166頁(yè))；

同書(shū)第35偈：

沒(méi)有付數(shù)或付數(shù)能被除數(shù)整除時(shí)，乘數(shù)[的解]為零，商當(dāng)認(rèn)為是付數(shù)除以除數(shù)所得結(jié)果([12]，202頁(yè))。

在此之前的印度數(shù)學(xué)家可能也意識(shí)到了這些關(guān)系，比如說(shuō)我們發(fā)現(xiàn)婆什迦羅一世盡管沒(méi)有明確說(shuō)明這條規(guī)則，但他在實(shí)際計(jì)算過(guò)程中會(huì)先同時(shí)約去b、c項(xiàng)的最大公因數(shù)，然后在解得x后再乘以這個(gè)公因數(shù)([5]，162頁(yè))。不管怎么說(shuō)，婆什迦羅二世將庫(kù)塔卡算法朝機(jī)械化和程序化的方向做了很大的推進(jìn)，依照他的規(guī)則我們已經(jīng)編寫(xiě)出了一套程序在計(jì)算機(jī)上實(shí)現(xiàn)了庫(kù)塔卡算法。

2 庫(kù)塔卡與大衍總數(shù)術(shù)異同比較

也許是出于歷法中計(jì)算歷元的需要，中國(guó)也從較早的年代開(kāi)始意識(shí)到不定分析問(wèn)題。公元4世紀(jì)前后的《孫子算經(jīng)》有“物不知數(shù)”題，便是要求解含有三個(gè)模數(shù)的同余式組N≡R1(moda1)≡R2(moda2)≡R2(moda3)。分析其中所給的算法術(shù)文，可以總結(jié)出中算的解法是先找出輔助系數(shù)K1，K2，K3，使如下同余式成立：

K1a2a3≡1(moda1)，K2a1a3≡1(moda2)，K3a1a2≡1(moda3)。

接著，所求的N便可由下式求得：

N≡R1K1a2a3+R2K1a1a3+R3K3a1a2(moda1a2a3)。

這種求解的程序后世稱呼為“孫子定理”或“中國(guó)剩余定理”。其中余數(shù)Ri和模數(shù)ai都是已知量，且ai兩兩互素。在數(shù)字相對(duì)簡(jiǎn)單的情況下，輔助系數(shù)Ki可以通過(guò)觀察試算得出；當(dāng)數(shù)字較復(fù)雜時(shí)，或是模數(shù)并非兩兩互素時(shí)，解的獲得就變得相當(dāng)困難。

中算文獻(xiàn)中真正完整的同余式組解法是秦九韶在其《數(shù)書(shū)九章》(1247)中所給出的“大衍總數(shù)術(shù)”。該術(shù)又可分為兩個(gè)大的部分，其一是約化模數(shù)的過(guò)程，即“化問(wèn)數(shù)(原模數(shù))為定數(shù)(約化后互素的模數(shù))”。其二是根據(jù)“定數(shù)”計(jì)算“乘率”，即上述輔助系數(shù)Ki，使得

Kigi≡1(modai)，(*3)，

其中g(shù)i被稱為“奇數(shù)”，是除ai以外的模數(shù)的乘積除以ai后的余數(shù)。通過(guò)這兩步求得乘率Ki后，就可以利用“孫子定理”求出最后的結(jié)果N。

大衍總數(shù)術(shù)中求乘率的步驟即為“大衍求一術(shù)”，其術(shù)文摘錄如下：

置奇右上，定居右下。立天元一于左上。先以右上除右下，所得商數(shù)與左上一相生，入左下。然后乃以右行上下，以少除多，遞互除之。所得商數(shù)，隨即遞互累乘，歸左行上下。須使右上末后奇一而止。乃驗(yàn)左上所得，以為乘率。[13]

下面就以問(wèn)題K×7≡1(mod25)為例，演示大衍求一術(shù)的解題過(guò)程。

(I)“置奇右上，定居右下。立天元一于左上”

奇數(shù)是7，定數(shù)為25，它們連同數(shù)字1按以下樣子排布：

1奇數(shù)7定數(shù)25

(II)“以右上除右下，所得商數(shù)與左上一相生，入左下”

即以定數(shù)25除以奇數(shù)7，所得余數(shù)4代替原來(lái)的被除數(shù)25放于右下，商3乘以除數(shù)的左邊這列中上方的數(shù)1后放入被除數(shù)左邊空位：

1725

25÷7=3…4→3×1=3

1734

(III)“然后乃以右行上下，以少除多，遞互除之。所得商數(shù)，隨即遞互累乘，歸左行上下。須使右上末后奇一而止”

將右列數(shù)字以小除大輾轉(zhuǎn)相除，余數(shù)替換被除數(shù)，商乘上除數(shù)左列數(shù)字后加入被除數(shù)左列數(shù)字。重復(fù)此過(guò)程直到右上位的數(shù)變?yōu)?為止：

1734

7÷4=1…3→1×3+1=4

4334

4÷3=1…1→1×4+3=7

4371

3÷1=2…1→2×7+4=18

18171

此時(shí)左上數(shù)字18便是乘率。經(jīng)檢驗(yàn)符合要求：18×7=126，126≡1(mod25)。

2.1 庫(kù)塔卡與大衍求一術(shù)解法異同

首先，可以將上面大衍求一術(shù)所要解決問(wèn)題的基本形式(*3)做一個(gè)變換，得到

數(shù)字列-1迭代計(jì)算數(shù)字列-2迭代計(jì)算(q1)q2q3?qn-1qn10K0=l=0,K1=m=1,K2=qnK1+K0=qn,K3=qn-1K2+K1=qn-1qn+1,…Kn+1=q1·Kn+Kn-1?！?jì)算方向01q1q2q3?qn-1qn計(jì)算方向↓J0=0,J1=1,J2=q1J1+J0=q1,J3=q2J2+J1=q1q2+1,…jn+1=qn·Jn+Jn-1。

沈康身已用數(shù)學(xué)歸納法證明了上面用固定庫(kù)塔卡和大衍求一術(shù)分別計(jì)算出的迭代結(jié)果兩者等價(jià)：Kn+1=Jn+1。[14]

庫(kù)塔卡(固定庫(kù)塔卡)和大衍求一術(shù)不光有著等價(jià)的問(wèn)題形式(二元一次不定方程)，通過(guò)上面的分析還能清楚看到兩者在解法上的相似性。具體來(lái)說(shuō)，它表現(xiàn)為：(1)兩者的基本思路都是通過(guò)輾轉(zhuǎn)相除的辦法將原不定方程系數(shù)化至最簡(jiǎn)，并利用此過(guò)程中得到的商數(shù)進(jìn)行迭代計(jì)算，而迭代的最后結(jié)果就是要求的解；(2)伴隨著相同的基本思路，兩種算法操作起來(lái)都有高度的機(jī)械化和程序化的特點(diǎn)，并且都規(guī)定了獨(dú)特的數(shù)字陣型(商的蔓和方陣)以保證運(yùn)算的正確和效率。

然而另一方面，庫(kù)塔卡和大衍求一術(shù)解法之間的差異也是很明顯的，主要表現(xiàn)在：(1)兩種解法的運(yùn)算順序不同，庫(kù)塔卡是先完成互除然后再進(jìn)行迭代，即將所有的商數(shù)列出后再?gòu)暮笸坝?jì)算，一氣呵成。大衍求一術(shù)則是除法和迭代同時(shí)進(jìn)行，隨除隨算，節(jié)省了數(shù)據(jù)儲(chǔ)存空間[15]。(2)庫(kù)塔卡沒(méi)有像大衍求一術(shù)那樣規(guī)定互除次數(shù)必須是偶數(shù)次。(3)在迭代計(jì)算的環(huán)節(jié)中大衍求一術(shù)實(shí)際規(guī)定了用于計(jì)算的頭兩項(xiàng)必須為0和1，而在固定庫(kù)塔卡，或者說(shuō)更一般的庫(kù)塔卡算法中則沒(méi)有這個(gè)限制條件，只要是滿足最后互除所得到的不定方程的解都可以。因而相比較而言，庫(kù)塔卡的計(jì)算過(guò)程更加自由和隨意一些。

2.2 庫(kù)塔卡解大衍總數(shù)術(shù)題

上節(jié)就庫(kù)塔卡(固定庫(kù)塔卡)與大衍求一術(shù)之間做了一番基于問(wèn)題形式和解法層面上的比較，比較的結(jié)果是兩者確實(shí)在算法結(jié)構(gòu)上有著諸多相似或是說(shuō)等價(jià)的地方。然而，如果我們換一個(gè)視角，即從解不定分析問(wèn)題這個(gè)目的出發(fā)就能意識(shí)到，庫(kù)塔卡的真正比較對(duì)象并不能僅局限于大衍求一術(shù)，而應(yīng)該是它的“母體”大衍總數(shù)術(shù)。前面的解說(shuō)中庫(kù)塔卡雖然大都以二元一次不定方程的形式呈現(xiàn)，但它其實(shí)和大衍總數(shù)術(shù)一樣，都是設(shè)計(jì)出用來(lái)解含有多個(gè)模數(shù)的一次同余式組，即已知N≡R1(moda1)≡R2(moda2)≡R3(moda3)≡…≡Rn(modan)，求N的問(wèn)題。至少?gòu)钠攀插攘_一世開(kāi)始印度人就已采取反復(fù)使用庫(kù)塔卡的方式來(lái)解決；中算雖有孫子的特殊情況(模兩兩互素)時(shí)的解法，但系統(tǒng)化的算法還需等到13世紀(jì)秦九韶的大衍總數(shù)術(shù)。換句話說(shuō)，庫(kù)塔卡雖然在算法上和大衍求一術(shù)有相似性，但它的解題能力其實(shí)等同于大衍總數(shù)術(shù)。為了說(shuō)明這一點(diǎn)，下面舉例看看如何用庫(kù)塔卡來(lái)解秦九韶的大衍問(wèn)題。

《數(shù)書(shū)九章》“大衍類”中的第八問(wèn)為“積尺尋源”題([13]，461頁(yè))，它可化為下面兩個(gè)同余式組：

N≡60(mod 130)≡30(mod 120)≡20(mod 110)≡30(mod 100)

≡30(mod 60)≡30(mod 50)≡5(mod 25)≡10(mod 20)；

M≡-60(mod 130)≡-10(mod 120)≡-30(mod 110)≡10(mod 100)

≡-10(mod 60)≡10(mod 50)≡10(mod 25)≡10(mod 20)。

以第一個(gè)關(guān)于N的同余式組為例，用大衍總數(shù)術(shù)解這道題時(shí)首先要對(duì)所有8個(gè)模數(shù)進(jìn)行約化，經(jīng)過(guò)“兩兩連環(huán)求等”約化后的同余式組為：

N≡60(mod 13)≡30(mod 8)≡20(mod 11)≡30(mod 3)≡5(mod 25)。

然后從它可以得到5個(gè)形如(*3)的單個(gè)同余式：

K1×9≡1(mod13)，K2×5≡1(mod8)，K3×1≡1(mod11)，K5×1≡1(mod3)，K7×7≡1(mod25)。

用大衍求一術(shù)分別求出解乘率Ki，再通過(guò)“孫子定理”得到最小整數(shù)解1230。

作為比較，我們?cè)囉脦?kù)塔卡來(lái)解此題。遵照婆什迦羅一世的做法，先取頭兩個(gè)同余關(guān)系，解同余式組N′≡60(mod130)≡30(mod120)，即有不定方程

此處系數(shù)a、b、c有共同的因數(shù)10，根據(jù)前述婆什迦羅二世《算法本源》26的規(guī)則，可將10約去，得到

用庫(kù)塔卡方法，先進(jìn)行互除：

13÷12=1……1，12÷1=12……0。

聰明數(shù)m和最后的商l為：

(0×m-3)÷1=l→m=7，l=-3。

商的蔓就為12，1，-3。經(jīng)一步迭代計(jì)算后得x′=9，因此y′=10，N′=1230。接著取頭兩個(gè)除數(shù)(模數(shù))130和120的最小公倍數(shù)1560作為新的除數(shù)(模數(shù))，N′作為對(duì)應(yīng)的余數(shù)，連同原式中的第三個(gè)同余式，解新同余式組N″≡1230(mod 1560)≡20(mod 110)：

此處121可被11整除，根據(jù)婆什迦羅二世《算法本源》35的規(guī)則，得x″=0，y″=11，N″=1230。類似地，可以發(fā)現(xiàn)1230≡30(mod100)≡30(mod60)≡30(mod 50)≡5(mod25)≡10(mod20)，因此最后的解N=1230。對(duì)于原題中的另一個(gè)關(guān)于M的同余式組，運(yùn)用與上面類似的方法也可以方便地求得M=3710，在此就不再展開(kāi)。

通過(guò)具體演算可以發(fā)現(xiàn)，用庫(kù)塔卡來(lái)解秦九韶題更為簡(jiǎn)單便捷，過(guò)程中實(shí)際只解了兩個(gè)不定方程。這主要是因?yàn)樵谑褂脦?kù)塔卡時(shí)可以直接對(duì)除數(shù)和余數(shù)進(jìn)行約化，因而無(wú)需考慮模數(shù)的互素性。此外，在阿耶波多-婆什迦羅一世的庫(kù)塔卡算法基礎(chǔ)上，婆羅摩笈多和婆什迦羅二世等人所補(bǔ)充的那些輔助規(guī)則對(duì)提高計(jì)算效率也非常有幫助。并且我們還看到，印度數(shù)學(xué)家能熟練使用0和負(fù)數(shù)進(jìn)行計(jì)算也是庫(kù)塔卡算法優(yōu)于大衍術(shù)的一個(gè)重要因素。

2.3 庫(kù)塔卡與大衍總數(shù)術(shù)之比較

正如沈康身先生指出“關(guān)于不定分析問(wèn)題中印互相影響，甚至師承關(guān)系問(wèn)題，素為海內(nèi)外學(xué)者所關(guān)注”。比如，印度數(shù)學(xué)史家森(S.N.Sen)和巴戈(A.K.Bag)就認(rèn)為中國(guó)大衍求一術(shù)來(lái)自印度，庫(kù)塔卡是一恰當(dāng)?shù)蔫b定根據(jù)([8]，361～362頁(yè)；[14]，267頁(yè))；李倍始卻持不同意見(jiàn)：“我們不能接受中國(guó)大衍求一術(shù)與印度庫(kù)塔卡有任何歷史淵源關(guān)系”。沈康身認(rèn)為對(duì)于這個(gè)問(wèn)題“不宜急于作出結(jié)論……(需要)對(duì)不定分析的來(lái)龍去脈各自在理論上和實(shí)際計(jì)算方法上的相同處和不同處進(jìn)行客觀分析和比較”([14]，267～268頁(yè))。因此，沈康身用“平行性”來(lái)描述中印兩民族的同余式研究。

就庫(kù)塔卡和大衍求一術(shù)而言，本文同意沈康身等學(xué)者對(duì)相似性的判斷，但具體細(xì)節(jié)有所不同。經(jīng)過(guò)對(duì)原典文獻(xiàn)的解讀和算法分析比對(duì)，我們指出庫(kù)塔卡的一種特殊類型，即固定庫(kù)塔卡的確與大衍求一術(shù)存在著算法結(jié)構(gòu)上的相似性和數(shù)學(xué)原理上的等價(jià)性。然而，兩者的“母體”，即庫(kù)塔卡和大衍總數(shù)術(shù)之間卻不存在著那樣的相似性，由此兩者間也很難存在淵源關(guān)系。雖然這個(gè)結(jié)論和李倍始的一致，但他的分析幾乎完全是基于現(xiàn)代數(shù)學(xué)認(rèn)識(shí)之上([8]，363～366頁(yè))，缺乏對(duì)算法原貌的重構(gòu)和歷史演變的分析。

本文認(rèn)為，應(yīng)該基于庫(kù)塔卡與大衍總數(shù)術(shù)展開(kāi)“中印同余問(wèn)題”的比較研究。

首先，庫(kù)塔卡是固定庫(kù)塔卡更加一般的形式，算法本質(zhì)上相同；大衍求一術(shù)卻是大衍總數(shù)術(shù)中的一個(gè)環(huán)節(jié)，與它之前的模數(shù)約化，以及之后用“孫子定理”求解的環(huán)節(jié)都緊密相連。換句話說(shuō)，庫(kù)塔卡可以看作是能對(duì)模數(shù)進(jìn)行約化處理的大衍求一術(shù)，其中接連使用聯(lián)立同余式的方法則可看成是“孫子定理”的一種表達(dá)。因而，庫(kù)塔卡和大衍總數(shù)術(shù)在總的結(jié)構(gòu)上沒(méi)有可比較之處，也不存在印度學(xué)者所主張的大衍求一術(shù)單獨(dú)借鑒庫(kù)塔卡的可能性。

再者，印度庫(kù)塔卡于5世紀(jì)首先出現(xiàn)在《阿耶波多歷算書(shū)》中以后，算法層面上基本沒(méi)有太大的變化，并且它一開(kāi)始就有處理任意一次同余問(wèn)題的能力。中國(guó)先是在3～4世紀(jì)時(shí)有處理模數(shù)兩兩互素的同余問(wèn)題的方法，但之后很長(zhǎng)時(shí)間沒(méi)有發(fā)展，直到13世紀(jì)秦九韶補(bǔ)充上了約化和求乘率(大衍求一術(shù))的規(guī)則形成大衍總數(shù)術(shù)后，才可以處理任意一般問(wèn)題。因而，庫(kù)塔卡和大衍總數(shù)術(shù)各自的發(fā)展歷史也是大不相同。

最后，也是在上述兩點(diǎn)的基礎(chǔ)上我們認(rèn)為，即便庫(kù)塔卡(固定庫(kù)塔卡)和大衍求一術(shù)有著一些相似性或等價(jià)性，但它不能說(shuō)明中印在此問(wèn)題上有過(guò)交流。這里的相似性很可能是不同文明在數(shù)學(xué)發(fā)展過(guò)程中的一種巧合，因?yàn)閮烧叩哪阁w——庫(kù)塔卡和大衍總數(shù)術(shù)——之間無(wú)論是從結(jié)構(gòu)上還是歷史上來(lái)說(shuō)都有著更加明顯的差異。并且，這種差異還體現(xiàn)在計(jì)算便捷性上，我們舉例說(shuō)明過(guò)庫(kù)塔卡要優(yōu)于大衍總數(shù)術(shù)，因而就這點(diǎn)來(lái)講也很難想象出兩者間有過(guò)傳播或借鑒。

當(dāng)然，庫(kù)塔卡與大衍總數(shù)術(shù)的相互獨(dú)立性，并不能否認(rèn)中印之間在其他數(shù)學(xué)知識(shí)和文化上存在相互交流與影響的可能性。

致 謝審稿過(guò)程中兩位專家和鄒大海研究員都為本論文提出了中肯切實(shí)又富有建設(shè)性的意見(jiàn)，謹(jǐn)此深表感謝!