大衍求一術實際筆算方法舉隅

秦九韶的「大衍求一術」，是初等數論裡同餘式計算裡絕不可少的方法，它比西方的方法簡便得多。這裡，記下筆者以前在書上學習的實際筆算方法，既是替自己備忘，也供有興趣的朋友參考。不過，這裡只是敘述具體算法，證明請恕從略。

 

　　設有Ａ和Ｂ兩個互素的正整數，如何尋得另一個正整數Ｋ，使得Ａ和Ｋ相乘後被Ｂ除的餘數恰好是１（換一個說法是Ａ乘Ｋ減１可被Ｂ整除）。「大衍求一術」就是幫助我們迅速尋找出這個Ｋ來的。其實，「大衍求一術」也是一種輾轉相除法，但看來更是巧妙神奇。

 

 

例一

求最小的正整數Ｋ，使之與23相乘後，被97除的餘數是1。

 

具體的「大衍求一術」筆算法：

 

23¹   23¹   3¹⁷    3¹⁷    1³⁸

97⁰   5⁴     5⁴     2²¹    2²¹

1      2      3      4      5

 

　　說明：先在第一欄把23寫在上方，並須在其右上角寫上１（這不是指數，我稱作「寄數」），97寫在下方，寄數必須是０。然後兩數中以小的一個作除數，先重覆的連寄數寫在第二欄上，本例裡，23是較小的，以之除97，商數是４，餘數是５，把餘數５寫在第二欄下方，其寄數是4×1＋0＝4（這裡４是剛求得的商數，１和０分別是23和97的寄數）。接下來以５作除數去除23，商數是４，餘數是３，所以在第三欄上方寫上３，其寄數是4×4＋1＝17（這裡的４和１分別是5和23的寄數）。接下來以３除５，商數是１，餘數是２，所以在第四欄下方寫上餘數２，其寄數是1×17＋4＝21，接下來，以２除３，商數是１，餘數是１，把餘數１寫在第五欄上方，其寄數是1×21＋17＝38。由於餘數１先在上方出現，算法到此結束，這１的寄數38就是我們所要求的最小整數Ｋ。

 

 

例二

求最小的正整數Ｎ，使之與97相乘後，被23除的餘數是1。

 

具體算法：

 

97¹   5¹     5¹     2⁵     2⁵

23⁰   23⁰   3⁴     3⁴     1⁹     1¹⁴

1      2      3      4      5      6

 

　　說明：先在第一欄把97寫在上方，寄數必須是１，23寫在下方，寄數必須是０，以小數除大數，商數是４，餘數是５，而５的寄數是4×0＋1＝1。接下來以５除23，商數是４，餘數是３，寄數是4×1＋0＝4。接下來以３除５，商數是１，餘數是２，寄數是1×4＋1＝5。接下來以２除３，商數是１，餘數是１，寄數是1×5＋4＝9。由於餘數１先在下方出現，按大衍求一術的規定，必須多算一步，（在第５欄裡）以下方的１除上方的２，商數是１，餘數是１，寄數是1×9＋5＝14。於是，14就是我們所求的最小正整數Ｎ。

 

 

更多的例子：

 

例三：某數與1989相乘後，被64除餘１。求滿足這題目的最小整數。

 

1989¹       5¹     5¹     1¹³

64⁰           64⁰   4¹²    4¹²

 

按上面的計算，此數為13。

 

 

 

例四：某數與64相乘後，被1989除餘１。求滿足這題目的最小整數。

 

64¹           64¹   4³⁷³  4³⁷³

1989⁰       5³¹    5³¹    1⁴⁰⁴  1¹⁵⁸⁵

 

按上面的計算，此數是1585。補充說明，由於餘數１首先出現在下方（第四欄），必須多算一步，以１除４，商數是３，餘數是１，寄數是3×404＋373＝1585。

 

 

例五：某數與1949相乘後，被101除餘１。求滿足這題目的最小整數。

 

1949¹       30¹           30¹   8⁷     8⁷     2²⁷    2²⁷

101⁰         101⁰         11³   11³   3¹⁰    3¹⁰    1³⁷    1⁶⁴

 

故所求之數是64。

 

 

 

例六：某數與101相乘後，被1949除餘１。求滿足這題目的最小整數。

 

101¹         101¹         11⁵⁸  11⁵⁸  3¹⁹³  3¹⁹³  1⁷¹⁴

1949⁰       30¹⁹          30¹⁹  8¹³⁵  8¹³⁵  2⁵²¹  2⁵²¹

 

故所求之數是714。

 

 

　　附帶一說，對於一般的一次同餘方程求解，「大衍求一術」亦是不可或缺的。比如下例：

                101Y ≣ 97           (mod1949)

這個方程相當於問某數Y乘101後以1949除之餘數是97，又或是某數Y乘101減97能被1949整除，求出這些Y來。它的一個解法就是先求出哪個最小正整數乘101減1能被1949整除，也就是先解同餘方程101K ≣ 1 (mod1949)，從上面的計算可知這個數是714，所以上述的一次同餘方程的解是：

 

                Y ≣ 97×714         (mod1949)

即            Y ≣ 1043             (mod1949)

驗算，101×1043－97確能被1949整除，而所有形如1043＋1949t（這裡t＝1, 2, 3…）的整數亦是這個一次同餘方程的解。