只知道几个余数,把那个数找回来
大衍求一术——一次同余方程组的通法,任意一组除数都管用,比高斯的《算术研究》早五百五十四年。
《孙子算经》里有一道「物不知数」:三三数之剩二,五五数之剩三,七七数之剩二,问物几何。它给了答案 23,也给了一条口诀,可那条口诀只对 3、5、7 这一组数管用,换一组就不知道该乘什么。秦九韶补上的正是这个「换一组怎么办」。《数书九章》开篇第一类就叫大衍,九道题,前面立着一套通法:把各个除数(元数)两两「连环求等」,把公因子约掉,化成两两互素的定数;定数相乘为衍母;衍母除以每个定数得衍数;衍数满定数去之,剩下的叫奇;再拿奇与定数去求一个乘率,使乘率乘奇除以定数正好余一;乘率乘衍数为用数;最后各个余数乘上自己的用数,加起来,满衍母去之,剩下的就是要找的那个数。求乘率的那一步就是「大衍求一术」,术文写得像一张棋谱:「置奇右上,定居右下,立天元一于左上……须使右上末后奇一而止」——两个数在右行辗转相除,商数交互累乘到左行,直到右上剩下一个 1,左上那个数就是乘率。这正是今天的扩展欧几里得算法,「求一」两个字说的就是「一直除到余数为一」。演示用的是卷二「余米推数」:米铺被盗,三箩米各剩一合、一升四合、一合,三个贼分别拿马杓(容一升九合)、木履(一升七合)、漆碗(一升二合)舀米。定数 19、17、12,衍母 3876,奇 14、7、11,乘率 15、5、11,用数 3060、1140、3553,三项相加得 22573,满衍母去之余 3193 合——每箩三石一斗九升三合,这正是书上的答数。欧拉与高斯后来各自给出过同余方程组的解法,但《算术研究》处理的是除数两两互素的情形;秦九韶的「连环求等」先把不互素的一组化成互素的定数,这一步欧洲要晚得多才补上。今天 RSA 解密用中国剩余定理把一次大指数拆成两次小的,快出约四倍;纠错码、散列表、日程排班,用的也是同一件事。
拨动三个余数,看求一术的算筹表一步步把乘率求出来,再合成那个数
《孙子算经》的「物不知数」只给了 3、5、7 这一组的口诀;秦九韶给的是通法。三个除数(定数)相乘得衍母;衍母除以每个定数得衍数;衍数满定数去之得奇;再用求一术求出乘率,使乘率乘奇除以定数正好余一;乘率乘衍数得用数——用数的妙处在于,它被自己那个定数除余一,被另外两个除都整尽。于是各余数乘上自己的用数一加,满衍母去之,剩下的就是要找的数。求一术那张表就是今天的扩展欧几里得算法:右行辗转相除,商数交互累乘进左行,「须使右上末后奇一而止」。
