大衍求一術(shù)初探

楊言紅

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

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

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

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

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

解：

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

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

解：

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

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

至此，我們發(fā)現(xiàn)大衍求一術(shù)的法則確實非同一般，古人的方法的確奧秘無窮值得我們深思研究。

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

使右上所得余數(shù)rm=1為止。

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

對上述結(jié)果用現(xiàn)代數(shù)學式子表示即：

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

當余數(shù)=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）

……

如此下去，由數(shù)學歸納法可得：rm=a·（-1）mKm（mod n），易知這里Km（m=1，2，3，…）均為正整數(shù)； 另外，我們還需要證明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為偶數(shù)時便有：a·Km≡1（mod n），由于0

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

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

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

當余數(shù)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即為所求乘率。

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

我們探討如下：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 ，我們發(fā)現(xiàn)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，……，）我們進一步發(fā)現(xiàn)關(guān)于最大公約數(shù)的一個定理的證明，即裴蜀定理的證明。如果在這里令b=n就得到rk=axk+byk，當然在這里沒有（a，b）=1的限制了，但算法仍然成立。由輾轉(zhuǎn)相除法我們知道：（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成立的一對整數(shù)數(shù)對（x，y）的算法程序，這也奠定了求解二元一次不定方程 ax+by=c的特解的算法程序。

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