大衍求一术初探

杨言红

【摘 要】本文初步研究了大衍求一术的古朴算法程序和其中的算法机理在现代同余式理论下的解释和联系，给出了大衍求一术算法程序中需要注意的若干问题并推导出了一个深刻的同余式递推公式，同时利用递推公式证明了裴蜀定理的一个新的证明，进一步探讨了二元一次同余式特解的一个算法程序。

【关键词】大衍求一术；乘率；一次同余式；辗转相除法；衍母；定母；算法程序；裴蜀定理；数学归纳法；二元一次不定方程

大衍求一术（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的特解的算法程序。

上面是我对大衍求一术算法及其理论根据的一些初探，望同行们对文中的错误和疑惑不惜指出，在此深表感谢之意。