作者 | 张影
来源 |《数学元年》
“大衍求一术”是中国古代数学的一项杰出成就，给出了求二元一次方程整数特解的有效方法。
本文介绍“大衍求一术”的算法与数学原理，适合中学生课外阅读。
(一)为什么需要“大衍求一术”？
“大衍求一术”算法是我国南宋数学家秦九韶在他的著作《数书九章》中提出的，用来求“孙子定理”中的“关键数”。
以《孙子算经》中的“物不知数”问题为例：
已知正整数 除以 的余数分别为求除以 的余数。
设已求得关键数 满足
则根据余数运算的原理，有
因为 分别是 的倍数，可知求 等价于求 使得
显然 符合要求，从而得到关键数
在后世的数学著作中，关键数通常利用歌诀来记忆。例如，明代数学家程大位在《算法统宗》中编写的歌诀为：
三人同行七十稀，
五树梅花廿一枝；
七子团圆正半月，
除百零五便得知。
“大衍求一术”的目标是破解这个关键问题，即：
求解一次同余式方程
其中 是互素的正整数。
(二)“大衍求一术”要意
对于互素的正整数对 “大衍求一术”算法实际上给出二元一次方程
的一组非负整数解
前文“怎样求最大公因数”(“数学元年”公众号2022年10月9日)，利用求最大公因数的更相减损过程，给出了求上述二元一次方程的一组非负整数解的简单的逐步提升算法。
秦九韶之所以要创造“大衍求一术”这样的新算法，是与中国古代数学的筹算技术密切相关的。
利用筹算进行求最大公因数的更相减损过程，不便于保留中间过程。因此更相减损过程停止后，实际上无法利用提升算法来逐步回退提升求解。
“大衍求一术”的优点是，随着辗转除法的进行，在第 步(设余数为 ) 得到 及 满足
最终，当辗转除法在第 步停止时(可能需要人为地增加一步调整除法)，刚好得到
因此 是 的一组解。
(三)“大衍求一术”的算法与解释
设 是互素的正整数。
改进的“大衍求一术”算法的目标是：求出方程
的一组非负整数解
算法每一步的结果是两行三列的数表，形如：
它的上下两行分别满足条件：
算法的初始状态设定为：
如果 则 满足要求。
设
前两步算法按 和 分情形说明。
情形一：
. 设 除以 的带余数除法的结果为：
用所得的商 分别去乘初始数表中对应于 的两数 并把结果加到对应于 的两数 上，再把 更新为余数 得到第1步的结果：
容易验证，数表的第一行的意义是：
. 如果 则算法结束。设 且 除以 的带余数除法的结果为：
用所得的商 分别去乘对应于 的两数 并把结果加到对应于 的两数 上，再把 更新为余数 得到第2步的结果：
容易确认，数表的第二行的意义是：
情形二：
. 设 除以 的带余数除法的结果为：
用所得的商 分别去乘初始数表中对应于 的两数 并把结果加到对应于 的两数 上，再把 更新为余数 得到第1步的结果：
容易确认，数表的第二行的意义是：
. 设 除以 的带余数除法的结果为：
用所得的商 分别去乘对应于 的两数 并把结果加到对应于 的两数 上，再把 更新为余数 得到第2步的结果：
容易确认，数表的第一行的意义是：
. 一般地，“大衍求一术”算法每一步的结果，或者形如
分别代表如下等式：
或者形如
分别代表如下等式：
. 这个过程一直进行下去，终止于
终止的条件是：数表的上行右列的数
5. 特别地，如果辗转相除的过程终止于下行的 (此时 ) 需要人为地增加一步“除法”，强制要求余数等于 即：
其中 算法随即终止，得到数表：
算法终止：此时，数表上行右列的数 从而有等式
这就得到了 的非负整数解
注：需要注意，秦九韶的“大衍求一术”的初始设定及每一步运行的结果都是两行两列的数表，只能求出所需的 的值。本文增添了中间一列，从而同时求出 的值。
(四)“大衍求一术”举例
本节通过例子，演示“大衍求一术”算法的过程。
例1求 的一组正整数解。
初始数表
| 0 | 20 |
| 0 | 27 |
第1步结果
| 0 | 20 |
| 7 |
第2步结果
67 第3步结果
6 第4步结果
| 23 | 17 |
因此得到一组正整数解 即有
例2求 的一组正整数解。
初始数表
| 0 | 96 |
| 0 | 67 |
第1步结果
| 29 | |
| 0 | 67 |
第2步结果
| 29 |
| 9 |
第3步结果
| 7 | 10 |
| 9 |
第4步结果
| 7 | 10 |
| 30 | 43 |
第5步结果
| 37 | 53 |
| 30 | 43 |
因此得到一组正整数解 即有
练习1求方程 的一组正整数解。
练习2求方程 的一组正整数解。
(五)“大衍求一术”原文
秦九韶《数书九章》第一卷的“大衍求一术”原文是：
大衍求一术云：置奇右上，定居右下。与天元一于左上。先以右上除右下，所得商数，与左上一相生，入左下。然后乃以右行上下，以少除多，递互除之，所得商数随即递互累乘，归左行上下。须使右上末后奇一而止。乃验左上所得，以为乘率。
需要注意，“除”的意思是“去除”，不是“除以”。
我国现行的中小学数学教科书，把“除以”简化为“除”，大谬。
了解“大衍求一术”原文的详细解读，可以参考：
沈康身《中国数学史大系·第五卷 两宋》第四章
关于“大衍求一术”原理的证明，可以参考：
万哲先《孙子定理和大衍求一术》高等教育出版社，1989.5
(六)结束语
“大衍求一术”为解一次同余式方程组提供了关键工具，从而在中国古代历法关于“上元积年”的计算中起着重要作用。
不过，明朝中叶以后，“大衍求一术”几乎失传，直到十九世纪才被考证重现，并稍加改进。
从现代数学的角度来看，“大衍求一术”可以帮助理解著名的矩阵群 的结构。
“大衍求一术”，汇古通今。它从历史中走来，引领我们踏进美丽的数学花园。
