大衍求一術初探

楊言紅

【摘 要】本文初步研究了大衍求一術的古樸算法程序和其中的算法機理在現代同余式理論下的解釋和聯系，給出了大衍求一術算法程序中需要注意的若干問題并推導出了一個深刻的同余式遞推公式，同時利用遞推公式證明了裴蜀定理的一個新的證明，進一步探討了二元一次同余式特解的一個算法程序。

【關鍵詞】大衍求一術；乘率；一次同余式；輾轉相除法；衍母；定母；算法程序；裴蜀定理；數學歸納法；二元一次不定方程

大衍求一術（dayanqiuyishu）是我國南宋數學家秦九韶（公元約1202——約1261年）繼前人造歷算法經驗在其所著的《數書九章》中提出的解一次同余式ax≡1（mod n），其中a， n為正整數，a

在一次同余式ax≡1（mod n）中a為正整數，a

例1：求同余方程33x≡1（mod74）之乘率。

解：

由于右上為1，故按大衍求一術的法則得乘率K=9，經驗算正確。

例2：求同余方程35x≡1（mod74）之乘率。

解：

解到這里我們發現，右下為1（而不是右上為1），如果再做除法，將有3÷1=3……0，從而得不到右上為1，從而似乎覺得按大衍求一術的法則得不到乘率，難道大衍求一術的法則錯了嗎？經過反復思考，我發現，如果右下為1，將其對應左下19變為-19代入同余式，結果正確，但顯然-19不是所求乘率（因為由定義乘率是個正整數），但-19≡55（mod 74），因此乘率K=55，顯然K=74-19，經檢驗正確。那么大衍求一術的法則有問題嗎？需要修改嗎？實際上大衍求一術的法則并沒有錯，也不需要修改，按法則我們的關鍵是得到右上為1即可，因此當我們得到右下為1時，可將3÷1=3……0 改為3÷1=2+1，以2充當商，1充當余數即可，上面的算法繼續下去為：

結果得到乘率K=55，與前述結果相一致。之所以如此是因為在做除法算式時，并非要嚴格求得余數，只不過這樣一來可能求出的是比乘率大的滿足同余方程的正整數，但可以除以定數取余得到乘率。

至此，我們發現大衍求一術的法則確實非同一般，古人的方法的確奧秘無窮值得我們深思研究。

下面我們用現代數學的語言研究大衍求一術的算法原理以釋其奧妙。先將大衍求一術的算法程序用下圖表示：

使右上所得余數rm=1為止。

此時左上所得Km即為 乘率，即K=Km，另外，當我們算到右下rm-1=1時，也可由K=n-Km-1求得K.下面我們對大衍求一術進行嚴格論證：

對上述結果用現代數學式子表示即：

n=aq1+r1 K1=q1×1+0=q1

a=r1q2+r2 K2=q2×K1+1

r1=r2q3+r3 K3=q3×K2+K1

…… ……

rm-2=rm-1qm+rm Km=qm×Km-1+Km-2

當余數=1時終止程序

由上述式子及同余式理論得：

r1=n-aq1≡（-1）1aq1（mod n）≡a·（-1）1K1（mod n）；

r2=a-r1q2≡a-a·（-1）1K1q2（mod n）≡a·（K1q2+1）（mod n）≡a·（-1）2K2（mod n）

r3=r1-r2q3≡a·（-1）1K1-a·（-1）2K2q3（mod n）≡a·（-1）3（q3K2+K1）（mod n）≡a·（-1）3K3（mod n）

……

如此下去，由數學歸納法可得：rm=a·（-1）mKm（mod n），易知這里Km（m=1，2，3，…）均為正整數； 另外，我們還需要證明0

n=aq1+r1=aK1+r1=（r1q2+r2）K1+r1=r1（q2K1+1）+r2K1=r1K2+r2K1=（r2q3+r3）K2+r2K1=r2（q3K2+K1）+r3K2=r2K3+r3K2=……=rm-1Km+rmKm-1

于是：n=rm-1Km+rmKm-1≥Km+Km-1>Km>0，即：0

于是當（1）rm=1，且m為偶數時便有：a·Km≡1（mod n），由于0

（2）rm=1，且m為奇數時便有a·（-Km）≡1（mod n），此時易知K=n-Km即為所求之乘率。至此，大衍求一術之奧妙已經明了。

明白了上述道理，下面我們將大衍求一術算法進一步改進如下表所述：

K0=0

r1=a，q1=0 K1=1

n=r1q2+r2 K2=K0-K1q2=-q2

r1=r2q3+r3 K3=K1-q3×K2

r2=r3q4+r4 K4=K2-q4K3

…… ……

rm-2=rm-1×qm+rm Km=Km-2-qmKm-1

當余數rm=1時終止程序

則：r1=a≡a·K1（mod n）

r2=n-r1q2≡-a·K1q2（mod n）≡a·（K0-K1q2）（mod n）≡a·K2（mod n）

r3=r1-r2q3≡a·K1-a·K2q3（mod n）≡a·（K1-q3K2）（mod n）≡a·K3（mod n）

……

rm≡a·Km（mod n），與上面不同的是這里的Km是正負相間的。

因此，當rm=1，注意到若Km+1>0，則K=Km+1為所求之乘率；若Km+1<0，則K=n+Km+1即為所求乘率。

下面我們繼續討論，如果將大衍求一術算法中的余數rm表述成ax+ny的形式，有何規律？

我們探討如下：r1=a=a×1+n×0；

r2=n-r1q2=a（-q2）+n×1=a×K2+n×1；

r3=r1-r2q3≡a-a·K2q3-n×q3≡a·（K1-q3K2）+n×（-q3） =aK3+n×（-q3）；

為了進一步論述，我們令x0=0，x1=1，y0=1，y1=0，且rk=axk+nyk，（k=1，2，……，）則有：

rk+1=axk+1+nyk+1， rk+2=axk+2+nyk+2，

于是：rk+2=rk-rk+1qk+2=（axk+nyk）-（axk+1+nyk+1）qk+2=a（xk-qk+2xk+1）+n（yk-qk+2yk+1），

故可令xk+2=xk-qk+2xk+1，yk+2=yk-qk+2yk+1，（k=0，1，2，……），對比Km=Km-2-qmKm-1，及K0=0，K1=1 ，我們發現xi=Ki（i=0，1，2，……），因此得到：rk=aKk+nyk（k=1，2，……m）。

于是我們又一次得到：rm=aKm+nym ≡a·Km（mod n）。

由表達式rk=axk+nyk，（k=1，2，……，）我們進一步發現關于最大公約數的一個定理的證明，即裴蜀定理的證明。如果在這里令b=n就得到rk=axk+byk，當然在這里沒有（a，b）=1的限制了，但算法仍然成立。由輾轉相除法我們知道：（a，b）=（rm-1，rm），因此當我們最后一步得到rm=0時終止算法，此時便有（a，b）=（rm-1，rm）=rm-1，且rm-1=axm-1+bym-1，或rm=1時終止算法，此時（a，b）=（rm-1，rm）=rm=1，且axm+bym=rm=1，故裴蜀定理成立，同時我們也得到了一個使（a，b）=ax+by成立的一對整數數對（x，y）的算法程序，這也奠定了求解二元一次不定方程 ax+by=c的特解的算法程序。

上面是我對大衍求一術算法及其理論根據的一些初探，望同行們對文中的錯誤和疑惑不惜指出，在此深表感謝之意。