大衍總數術曰:置諸問數,一曰元數,二曰收數,三曰通數,四曰復數。元數者,先以兩兩連環求等,約奇弗約偶,或元數俱偶,約畢可存一位見偶。或皆約而猶有類數存,姑置之,俟與其他約徧,而後乃與姑置者求等約之。或諸數皆不可盡類,則以諸元數命曰復數,以復數格入之。收數者,乃命尾位分釐作單零,以進所問之數,定位訖,用元數格入之。或如意立數爲母,收進分釐,以從所問,用通數格入之。通數者,置問數通分内,予互乘之,皆曰通數。求總等,不約一位,約眾位,得各元法數,用元數格入之。或諸母數繁,就分從省通之者,皆不用元,各母仍求總等,存一位,約眾位,亦各得儿法數,亦用元數格入之。復數者,問數尾位見十以上者,以諸數求總等,存一位,約眾位,始得元數。
以定相乘爲衍母,以各定約衍母,各得衍數。
諸衍數各滿定母去之,不滿曰奇。以奇與定用大衍求一入之,以求乘率。
大衍求一術云:置奇右上,定居右下,立天元一於左上,先以右上除右下,所得商數,與左上一相生入左下,然後乃以右行上下,以少除多,遞互除之,所得商數,隨卽遞互累乘,歸左行上下,須使右上末後奇一而止,乃騐左上所得,以爲乘率。或奇數已見單一者,便爲乘率。置各乘率,對乘衍數,得泛用,併泛課衍母多一者,爲正用。或泛多衍母倍數者,騐元數奇偶同類者,損其半,各爲正用數。或定母得一而衍數同衍母者,爲無用數。當騐元數同類者,而正用至多處借之,以元數兩位求等,以等約衍母爲借數,以借數損有以益其無,爲正用。或數處無者,如意立數爲母,約衍母所得,以如意子乘之,均借補之。或欲從省,勿借,任之爲空可也。然後其餘各乘正用,爲各總。
併總滿衍母去之,不滿爲所求率數。
類名有四。謂尾位見單零者,本門揲蓍、酒息、斛糶、砌甎失米之類是也。謂尾位見分釐者,假令冬至三百六十五日二十五刻,欲與甲子六十日爲一會,而求積日之類。謂諸數各有分子母者,本門問一會積年是也。謂尾位見十或百及千以上者,本門築堤并急足之類是也。或約得五而彼有十,乃約偶而弗約奇。
或列各定爲母,于右行,各立天元一爲子,丁左行,以母互乘子,亦得衍數。
或奇得一者,便爲乘率。
或三處同類,以二約衍母,于三處損之。
位\nColumn | 定母 / 元数\nModulus | 奇 / 余\nResidue | 乘率 / 用数\nMultiplier |
|---|---|---|---|
| 奇 | Mi mod mi | 衍数除定母后的余数 | 用来求乘率 |
| 定 | mi | 每一项的模数 | 右下位 |
| 衍数 | M / mi | 衍母除以定母 | 先满定母去之 |
| 乘率 | ti | 使奇数乘后余一的数 | 扩展欧几里得 |
| 满去 | mod | 满衍母或定母即除去 | 取余 |
| 余 | remainder | 不满所余之数 | 合并后答案 |
术语对照
设各定母为 m1, m2, ..., mk,衍母 M = m1 m2 ... mk。
对每个 i,衍数 Mi = M / mi。它能被其他定母整除,但通常不能被 mi 整除。
大衍求一术要求乘率 ti,使 Mi × ti ≡ 1 (mod mi)。这一步就是扩展欧几里得算法。
若题目给出余数 ai,则合并数满足 x ≡ Σ ai Mi ti (mod M)。这就是现代中国剩余定理的构造式。
秦九韶没有写同余符号,也没有写“逆元”这个现代词。他的“置奇右上,定居右下,立天元一于左上”,是在筹算格上反复做辗转相除,求出今天记作 Mi^{-1} mod mi 的乘率。