呂 鵬 紀志剛

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

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

1 庫塔卡算法詳解

庫塔卡問題的代數(shù)表達式為：

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

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

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

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

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

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

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

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

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

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

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

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

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

緊接著文字注釋，婆什迦羅又輔以多道例題來進一步演示庫塔卡的解法。如其第2題為：

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

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

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

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

31 ÷ 12=2……7。

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

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

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

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

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

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

即通過試商找出一數(shù)m，使得它與最后的余數(shù)2的乘積加上原來余數(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

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

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

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

4 × 1+2=6。

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

164

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

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

6× 1+4=10。

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

106

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

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

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

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

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

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

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

1.2 庫塔卡算法的一般步驟及其證明

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

來演示庫塔卡算法的一般運算程序，其目的是求“乘數(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ù)第二項乘以倒數(shù)第三項，積加上倒數(shù)第一項，所得的和取代原來倒數(shù)第三項，并消去最后一項：

q2?qi-2qi-1qi

→

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

→

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

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

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

?

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

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 含三個及以上模數(shù)的同余式組的解法

上面1.1節(jié)的庫塔卡例題涉及到的是已知某數(shù)分別除以兩個除數(shù)得到相應(yīng)余數(shù)時如何來求這個數(shù)。當除數(shù)(即同余式組中的模數(shù))有三個或三個以上時，仍可用庫塔卡來解，正如前面所引婆羅摩笈多的話：“可以計算出三個或更多行星的會合周期”。至于具體如何操作，我們援引普利突大卡在注釋《體系》這部分時所提供的一道例題([1]，326頁)：

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

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

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

由于這里余數(shù)為0，所以(iii)中要找的聰明數(shù)m可以取任意值，這是因為：

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

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

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

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

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

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

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

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

N2=30×1+29=59。

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

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

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

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

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

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

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

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

同書第35偈：

沒有付數(shù)或付數(shù)能被除數(shù)整除時，乘數(shù)[的解]為零，商當認為是付數(shù)除以除數(shù)所得結(jié)果([12]，202頁)。

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

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

也許是出于歷法中計算歷元的需要，中國也從較早的年代開始意識到不定分析問題。公元4世紀前后的《孫子算經(jīng)》有“物不知數(shù)”題，便是要求解含有三個模數(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)。

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

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

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

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

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

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

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

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

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

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

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

即以定數(shù)25除以奇數(shù)7，所得余數(shù)4代替原來的被除數(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ù)此過程直到右上位的數(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ù)字18便是乘率。經(jīng)檢驗符合要求：18×7=126，126≡1(mod25)。

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

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

數(shù)字列-1迭代計算數(shù)字列-2迭代計算(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?！嬎惴较?1q1q2q3?qn-1qn計算方向↓J0=0,J1=1,J2=q1J1+J0=q1,J3=q2J2+J1=q1q2+1,…jn+1=qn·Jn+Jn-1。

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

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

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

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

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

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

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)。

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

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

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

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

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

作為比較，我們試用庫塔卡來解此題。遵照婆什迦羅一世的做法，先取頭兩個同余關(guān)系，解同余式組N′≡60(mod130)≡30(mod120)，即有不定方程

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

用庫塔卡方法，先進行互除：

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)一步迭代計算后得x′=9，因此y′=10，N′=1230。接著取頭兩個除數(shù)(模數(shù))130和120的最小公倍數(shù)1560作為新的除數(shù)(模數(shù))，N′作為對應(yīng)的余數(shù)，連同原式中的第三個同余式，解新同余式組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。對于原題中的另一個關(guān)于M的同余式組，運用與上面類似的方法也可以方便地求得M=3710，在此就不再展開。

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

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

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

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

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

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

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

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

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

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