第十章 不定問題
第四節 大衍總數術與大衍求一術
由於19、17、12兩兩互素,便為定數。衍母為19×17×12=3876,衍數依次是17×12=204,19×12=228,19×17=323。求分別滿足k1×204≡1(mod 19),k2×228≡1(mod 17),k3×323≡1(mod 12)的乘率k1,k2,k3。由於衍數分別大於定數,便用定數減衍數,得奇數14,7,11。問題變成求分別滿足k1×14≡1(mod 19),k2×7≡1(mod 17),k3×11≡1(mod 12)的k1,k2,k3。求k1的程序:
於是N≡1×15×204+14×5×228+1×11×323(mod 3876)≡22573(mod 3876)=3193.

歐洲現代數學大師歐拉(公元1707—1783年)、拉格郎日(公元1736—1813年)都對同余式問題作過研究。高斯(公元1777—1855年)的《算術探究》(公元1801年)中明確寫出了上述定理。來華傳教士偉烈亞力(公元1815—1887年)1852年將「物不知數」題介紹到西方,人們發現它與上述定理一致,遂稱之為中國剩餘定理。
這裏要計算到右上rn=1,故有「求一」之名。可以證明,這種求乘率k的方法是正確的。在上述方法中,諸Ai必須是兩兩互素的正整數,但是在實際問題中諸Ai不一定互素,甚至不一定是整數,可能是分數或小數。秦九韶針對不同的情況,提出了化約各種不同的問題為定數的程序。由於中國古代沒有因數分解的概念,化約過程走了彎路,但畢竟比較成功地解決了這個問題。
若Ai(i=1,2……)是兩兩互素的正整數,Ri<Ai,Ri也是正整數(i=1,2……),正整數N滿足同余式組
中國民間歷來流傳著「秦王暗點兵」、「韓信點兵」、「鬼谷算」、「隔牆算」、「剪管術」等數字遊戲,實際上都是一種方法,它導源於《孫子算經》「物不知數」問,秦
https://read.99csw.com九韶稱作「大衍總數術」,即今之一次同余式組解法。同余是數論中的一個重要概念,給定一個正整數m,如果二整數a、b,使a-b被m整除,就稱a、b對模m同余,記作a≡b(mod m)。「物不知數」題是:「今有物不知數,三三數之剩二,五五數之剩三,七七數之剩二,問物幾何?」這是世界數學史上首次提出同余式問題。用現代符號表示,此題是求滿足同余式:N≡2(mod 3)≡3(mod 5)≡2(mod 7)的最小正整數N。《孫子算經》的解法是
N≡Ri(mod Ai)i=1,2……如果能找到諸正整數ki,使
N≡1(mod 19)≡14(mod 17)≡1(mod 12)
秦九韶把大衍總數術不僅用於曆法推算,而且用於建築、行程、粟米交易、庫額利息,甚至斷案等問題。謹以「余米推數」問為例。有一米鋪投訴被盜去三籮筐米,不知數量。左籮剩1合,中籮剩14合,右籮剩1合。后捉到盜米賊甲、乙、丙。甲說,當夜他摸得一隻馬杓,一杓杓將左籮的米舀入布袋;乙說,他踢著一隻木履,將中籮的米舀入布袋;丙說,他摸得一隻漆碗,將右籮的米舀入布袋。三人將米拿回家食用,日久不知其數,遂交出作案工具。量得一馬杓容19合,一木履17合,一漆碗
https://read.99csw.com12合。問共丟失的米數及三人所盜的米數。這是求同余式組的解N。
其根據是:70=2×5×7≡1(mod 3),21=3×7≡1(mod 5),15=3×5≡1(mod 7)。可見《孫子算經》的作者在一定程度上明白了下面這個定理:
每籮米數3193合,甲、丙盜米各為3192合,乙盜米3179合,共盜米9563合。

求k3的程序:
秦九韶的方法稱為大衍總數術。他將諸ki叫作乘率,諸Ai叫作定數,
叫作衍母,
叫衍數,而方法的核心是大衍求一術,即求乘率ki的方法。為敘述方便,我們將
記為G,將Ai記為A,ki記為k,求一術變成在A、G互素的情況下求滿足kG≡1(mod A)的k值。秦九韶首先提出,如果G>A,若G≡g(mod A),0<g<A,則kg≡1(mod A)與kG≡1(mod A)等價,這便是現代同余式理論中的傳遞性。因此問題變成了求滿足kg≡1(mod A)的k。秦九韶稱g為奇數。他的大衍求一術是:將g置於右上,A置於右下,左上置天元一,g與A輾轉相除,商依次是q1、q2……餘數是r1、r2……按一定規則在左下、左上計算c1、c2……直到右上rn=1為止(此時n必定是偶數),則左上的cn=qncn-1+cn-2便是所求的k值。用現代符號表示就是:read•99csw•com
叫作衍母,
叫衍數,而方法的核心是大衍求一術,即求乘率ki的方法。為敘述方便,我們將
記為G,將Ai記為A,ki記為k,求一術變成在A、G互素的情況下求滿足kG≡1(mod A)的k值。秦九韶首先提出,如果G>A,若G≡g(mod A),0<g<A,則kg≡1(mod A)與kG≡1(mod A)等價,這便是現代同余式理論中的傳遞性。因此問題變成了求滿足kg≡1(mod A)的k。秦九韶稱g為奇數。他的大衍求一術是:將g置於右上,A置於右下,左上置天元一,g與A輾轉相除,商依次是q1、q2……餘數是r1、r2……按一定規則在左下、左上計算c1、c2……直到右上rn=1為止(此時n必定是偶數),則左上的cn=qncn-1+cn-2便是所求的k值。用現代符號表示就是:read•99csw•comread.99csw.com
同余式解法還來自於曆法制定中上元積年的計算。中國古代的曆法,要假定遠古有一個甲子日,那一年的冬至與十一月的合朔都恰好在這一日的子時初刻。有這麼一天的年度叫上元,從上元到制定曆法的本年的總年數叫上元積年。已知本年冬至時刻及十一月平朔時刻,求「上元積年」在數學上便是同余式問題。但是,「歷家雖用,用而不知」(《數書九章序》),在中國數學史也是世界數學史上第一次提出一次同余式組完整解法的是南宋數學家秦九韶。
N=2×70+3×21+2×15-2×105=23。



求k2的程序: