楊言紅

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

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

大衍求一術(shù)（dayanqiuyishu）是我國南宋數(shù)學(xué)家秦九韶（公元約1202——約1261年）繼前人造歷算法經(jīng)驗(yàn)在其所著的《數(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)驗(yàn)算正確。

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

解：

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

結(jié)果得到乘率K=55，與前述結(jié)果相一致。之所以如此是因?yàn)樵谧龀ㄋ闶綍r，并非要嚴(yán)格求得余數(shù)，只不過這樣一來可能求出的是比乘率大的滿足同余方程的正整數(shù)，但可以除以定數(shù)取余得到乘率。

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

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

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

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

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

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

當(dāng)余數(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ù)學(xué)歸納法可得：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

于是當(dāng)（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ù)算法進(jìn)一步改進(jìn)如下表所述：

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

當(dāng)余數(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是正負(fù)相間的。

因此，當(dāng)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）；

為了進(jìn)一步論述，我們令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）。

由表達(dá)式rk=axk+nyk，（k=1，2，……，）我們進(jìn)一步發(fā)現(xiàn)關(guān)于最大公約數(shù)的一個定理的證明，即裴蜀定理的證明。如果在這里令b=n就得到rk=axk+byk，當(dāng)然在這里沒有（a，b）=1的限制了，但算法仍然成立。由輾轉(zhuǎn)相除法我們知道：（a，b）=（rm-1，rm），因此當(dāng)我們最后一步得到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ù)的一些初探，望同行們對文中的錯誤和疑惑不惜指出，在此深表感謝之意。