作者 | 張影
來源 |《數學元年》
「大衍求一術」是中國古代數學的一項傑出成就，給出了求二元一次方程整數特解的有效方法。
本文介紹「大衍求一術」的演算法與數學原理，適合中學生課外閱讀。
(一)為什麼需要「大衍求一術」？
「大衍求一術」演算法是我國南宋數學家秦九韶在他的著作《數書九章》中提出的，用來求「孫子定理」中的「關鍵數」。
以《孫子算經》中的「物不知數」問題為例：
已知正整數 除以 的餘數分別為求除以 的餘數。
設已求得關鍵數 滿足
則根據餘數運算的原理，有
因為 分別是 的倍數，可知求 等價於求 使得
顯然 符合要求，從而得到關鍵數
在後世的數學著作中，關鍵數通常利用歌訣來記憶。例如，明代數學家程大位在《演算法統宗》中編寫的歌訣為：
三人同行七十稀，
五樹梅花廿一枝；
七子團圓正半月，
除百零五便得知。
「大衍求一術」的目標是破解這個關鍵問題，即：
求解一次同餘式方程
其中 是互素的正整數。
(二)「大衍求一術」要意
對於互素的正整數對 「大衍求一術」演算法實際上給出二元一次方程
的一組非負整數解
前文「怎樣求最大公因數」(「數學元年」公眾號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
(六)結束語
「大衍求一術」為解一次同餘式方程組提供了關鍵工具，從而在中國古代曆法關於「上元積年」的計算中起著重要作用。
不過，明朝中葉以後，「大衍求一術」幾乎失傳，直到十九世紀才被考證重現，並稍加改進。
從現代數學的角度來看，「大衍求一術」可以幫助理解著名的矩陣群 的結構。
「大衍求一術」，匯古通今。它從歷史中走來，引領我們踏進美麗的數學花園。
