大衍求一术

        今有物,不知其数。三、三数之,剩二;五、五数之,剩三;七、七数之,剩二。问物几何?
        术曰:三、三数之剩二,置一百四十;五、五数之剩三,置六十三;七、七数之剩二,置三十。并之,得二百三十三。以二百一十减之,即得。凡三、三数之剩一,则置七十;五、五数之剩一,则置二十一;七、七数之剩一,则置十五。一百六以上,以一百五减之,即得。
        

南北朝《孙子算经》卷下

        【评】此“物不知数”问是中国数学史上第一次明确提出的一次同馀式组问题。根据题设,它是求满足同余式组N≡2(mod3)≡3(mod5)≡2(mod7)的最小正整数N。其解答为N=2×70+3×21+2×15-2×105=23,并说明了70,21,15的选择为70≡1(mod3),21≡1(mod5),15≡1(mod7)。此题的解法符合剩馀定理。十九世纪,英国传教士伟烈亚力将其介绍到西方,则其解法称为中国剩馀定理。
        大衍总数术曰:置诸问数。(原注:类名有四。)一曰元数。(原注:谓尾位见单零者。本门揲蓍、酒息、斛粜、砌砖、失米之类是也。)二曰收数。(原注:谓尾位见分厘者。假令冬至三百六十五日二十五刻,欲与甲子六十日为一会而求积日之类。)三曰通数。(原注:谓诸数各有分子、母者。本门问一会积年是也。)四曰复数。(原注:谓尾位见十、或百及千以上者。本门筑堤并急足之类是也。) ^①
        元数者,先以两两连环求等,约奇弗约偶。(原注:或约得五,而彼有十,乃约偶而弗约奇。)或元数俱偶,约毕可存一位见偶;或皆约而犹有类数存,姑置之,俟与其他约遍,而后乃与姑置者求等约之。或诸数皆不可尽类,则以诸元数命曰复数,以复数格入之。
        收数者,乃命尾位分厘作单零,以进所问之数。定位讫,用元数格入之。或如意立数为母,收进分厘,以从所问,用通数格入之。
        通数者,置问数,通分内子,互乘之,皆曰通数。求总等,不约一位,约众位,得各元法数,用元数格入之。或诸母数繁,就分从省通之者,皆不用元,各母仍求总等,存一位,约众位,亦各得元法数,亦用元数格入之。
        复数者,问数尾位见十以上者,以诸数求总等,存一位,约众位,始得元数。两两连环求等,约奇弗约偶,复乘偶;或约偶弗约奇,复乘奇,皆续等,下用之。或彼此可约,而犹有类数存者,又相减以求续等,以续等约彼,则必复乘此,乃得定数。所有元数、收数、通数三格,皆有复乘求定之理,悉可入之 ^②。
        求定数,勿使两位见偶,勿使见一太多。见一多则借用繁,不欲借,则任得一,以定相乘为衍母,以各定约衍母,各得衍数。(原注:或列各定为母于右行,各立天元一为子于左行,以母互乘子,亦得衍数。) ^③
        诸衍数,各满定母,去之。不满曰奇,以奇与定,用大衍求一入之,以求乘率。(原注:或奇得一者,便为乘率。) ^④
        大衍求一术云:置奇右上,定居右下,立天元一于左上。先以右上除右下,所得商数,与左上一相生,入左下,然后乃以右行上下,以少除多,递互除之,所得商数,随即递互累乘,归左行上下,须使右上末后奇一而止,乃验左上所得,以为乘率。或奇数已见单一者,便为乘率 ^⑤。
        置各乘率,对乘衍数,得泛用。并泛,课衍母。多一者为正用;或泛多衍母倍数者,验元数奇偶同类者,损其半倍,(原注:或三处同类,以三约衍母,于三处损之。)各为正用数。或定母得一,而衍数同衍母者,为无用数,当验元数同类者,而正用至多处借之。以元数两位求等,以等约衍母为借数。以借数损有以益其无,为正用。或数处无者,如意立数为母,约衍母,所得,以如意子乘之,均借补之。或欲从省,勿借任之为空,可也。然后,其馀各乘正用,为各总。并总,满衍母去之。不满,为所求率数 ^⑥。
        

宋·秦九韶《数书九章·大衍类》

        [注]①此为秦九韶对问数的分类及界定。分成一般正整数、小数、分数、十的倍数四类,分别称为元数、收数、通数、复数。②以上四段,秦九韶针对各种不同的问数,给出了“求总等,不约一位约众位”、“两两连环求等,约奇弗约偶,或约偶弗约奇”、“求续等,以续等约彼则必复乘此”等三种处理方法,将非两两互素的问数化成两两互素即两两无等数的定数,使各定数分别是相应问数的因子,各定数之积是诸问数的最小公倍数,以应用大衍求一术,并最后计算出满足同馀式组的答案。③此是对以上四条的补充。④这是秦九韶提出的一个重要命题:如果G>a,G≡g(moda),0<g<a,则同馀式kg≡1(moda)与KG≡1(moda)等价。因此可由g与α求乘率k。g称为奇数。⑤这是同馀式解法的核心。由g,a辗转相除,其算法用现代符号表示便是:

当n是偶数时,c _n便是所求的乘率k。⑥设原问题化成同馀
        式是N≡R ₁(modA ₁)≡R ₂(modA ₂)≡……≡R _n(modA _n),诸A _i为问数,诸R _i为正用。化成N≡R ₁ (moda ₁)≡R ₂(moda ₂)
        ≡……≡R _n(modax),诸a _i两两互素,为定数,诸a _i的连乘积M称为衍母,称为衍数,诸称为泛用,诸称为各总,那么,(modM)即所求。这就是所谓剩馀定理。
        【评】秦九韶在中国数学史上第一次系统叙述了一次同馀式解法,许多成就是十八、十九世纪世界数学大师高斯等才达到的水平。由于中国古代没有素数理论,他在化非两两互素的问数为两两互素的定数的方法上走了某些弯路,也有失误,但他开辟草莱的功绩是不可抹煞的。
        自《孙子算经》“物不知数”一题有术无草,后人罕通其妙,遂无有论及者。宋秦氏道古以大衍释之,其法始显。
        国朝骆氏春池 ^①、张氏古愚各有专书,然求等约分,头绪不一,初学茫然。近日时君清浦 ^②《求一术指》立法稍简,亦仅识其当然,而于所以然终阙如也。同治癸酉左君壬叟 ^③衍《通分捷法》一帙,将分母、分子析为各数根,任以多项通分,顷刻可得,可谓善于求较者矣。余因悟大衍术析各泛母以求定母,形迹显露,术理朗然,较之旧术,简而愈详。
        

清·黄宗宪《求一术通解·序》

        [注]①清骆腾风著《艺游录》,张敦仁著《求一算术》,均讨论大衍求一术。②即时曰醇。③即左潜。
        【评】黄宗宪概述了到他为止大衍求一术的历史及秦九韶等学者的贡献。
        今有数不知总。任命一数累减之。(原注:或有剩,或无剩。)复易一数累减之。(原注:或有剩,或无剩。)再易一数累减之。(原注:或有剩,或无剩。)欲求总数,其术如何?
        答曰:答数无穷。(原注:理固如是,然各题所求,总以初答为主。)
        按:此指三次减数,即《孙子》原术也。凡制题,自两次以至多次,皆可任意命数,求法不殊。
        术曰:置各减数,分行列之,曰泛母。析泛母(原注:析法详后),为诸数根 ^①。(原注:凡二、三、五、七,及不能成幂之数,皆曰数根。)以求定母。(原注:求法详后。)各定母连乘,为衍母。复以定母除衍母,得其衍数。(原注:或以馀位定母连乘,亦得本位衍数。)再以定母累减衍数以求一。其初次减得一者,即以衍数为用数。若初次未减得一者,则辗转互减以求之,必至衍数得一而止。其所寄数(原注:求法详后)为乘率,以乘衍数得用数。仍分位列之为一表。乃视题中某位剩数若干,(原注:某位无剩数,则弃之不用。)以本位用数乘之为总数。逐位求总数毕,乃并之为所求率。每减衍母一次得一答。不足减者即初答。(原注:若每加衍母,则答数无穷。)
        析泛母法
        置各行泛母为实,先以二、三、五、七各小根为法,逐行分次累除之,至四小根皆不受除,乃验不受除之数,皆成根即止。或有未成根者,则以除得之根为法除之,至皆不受除,再验不受除之数,皆成根即止。抑或有未成根又不受已得各根之除者,以未成根之数求等,以等为法除之,至各数皆无等而止。书其末次得数,及每次用以为法之数于本位下,是为诸根。
        求定母法
        前法析泛母毕,乃遍视各同根,(原注:如三与三,五与五之类。)取某行最多者用之。馀行所有,弃之不用。再视本行所有异根,(原注:如三与五之类。)或少于他行,则弃之。(原注:因他行已用,则此行必弃。)抑或多于馀行,亦用之。或于他行最多者等,则此两行随意用之。(原注:用此则弃彼,用彼则弃此。)以所用数根连乘之,即得本行定母。若某行各根皆少于他行者,则此位无定母。
        求寄数法
        列定母于右行,列衍数于左行。(原注:左角上预寄一数。按:预寄一数者,是记此一个衍数也。原书谓之立天元一。)辗转累减,(原注:凡定母与衍数辗转累减,则其上所寄数必辗转累加。至衍数馀一即止。视左角上寄数为乘率。(原注:若求反乘率,至定母馀一即止。视右角上寄数为反乘率。)
        按:两数相减,必以少数为法,多数为实。其法上无寄数者,不论减若干次,减馀数上仍以一为寄数。其实上无寄数者,减馀数上以所减次数为寄数。其法上实上俱有寄数者,视累减若干次,以法上寄数亦累加若干次于实上寄数中,即得减馀数上之寄数矣。
        

清·黄宗宪《求一术通解》卷上

        [注]①数根即素因子。
        【评】黄宗宪在前人工作的基础上,采用将模数分解成素因数的方法求定数,克服了秦九韶因为没有素数概念所走的弯路及失误,圆满地解决了大衍求一术的求定数问题。