中国剩余定理 最简易、工作量最小的算法：“化为相同除数”法

                  就我所知，“中国剩余定理”有五种解法：

一、枚举法

二、解不定方程法

三、逐级满足法

四、化为相同除数法、

五、典经的、“大衍求一术”解法

在五种解法中，我认为最简易、工作量最小的解法，就是“化为相同除数法”。

 下面依“孙子问题”中的经典问题为例，作一演算：

“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何。”即：

 A≡2  (Mod 3 )  →    A÷3 ＝ ☆(整数) … 2   ( 三三数之剩二 )     

             A≡3  (Mod 5 )  →    A÷5 ＝ ☆        … 3   ( 五五数之剩三 )     

A≡2  (Mod 7 )  →    A÷7 ＝ ☆        … 2   ( 七七数之剩二 )    

求A

 

解算步骤：

1     先用乘法，使它们的除数相同，成为一组等价的不定方程组。

A÷ 3 ＝ X … 2    ×5×7 →  35A÷105 ＝ X  余70  …  (1)    

          A÷ 5 ＝ Y … 3    ×3×7 →  21A÷105 ＝ Y  余63  …  (2)       

A÷ 7 ＝ Z … 2    ×3×5 →  15A÷105 ＝ Z  余30  …  (3)   

注：除数3、5、7的最小公倍数是3×5×7＝105，就拿105作为相同的除数。为此，各式乘一个其他除数的公倍数(可以叫局部公倍数)，如第一式乘(5×7＝) 35，35就是第二式、第三式的公倍数。等等。由于整式乘一个数，所以商不变。商X、Y、Z，除了必须是整数外，与解题结果无关。所以以后只用整数K表示商就可以了。在同余式中，就根本不没有商的位置。

这样，联立方程组中的除数，都为最小公倍数105，除数相同了。

 

2       利用“同余式”的和差特性，通过加减，将联立方程组变为一个不定方程式。

各式如何加减，有多种选择。如：

一      (1)＋ (2) ＋(3)   → (21＋15＋35) A÷105 ＝ K  余(63＋30＋70)  →

71A÷105 ＝ K  余163  …  (4)

注：这里余数超过除数，可转化余数，等效为 71A÷105 ＝K  余58 (＝163－105) … (5)

解不定方程式 (4) 或 (5)，都得A=23 。

为简单起见，以后可以不必转化余数，直接解方程式 (4) 就行了。

至于如何解71A÷105 ＝ K  余163 呢？ 见下面第3步骤。

二      (2)＋(3)－(1)  →  (21+15－35) A÷105 ＝K   余 (63＋30－70)  →

1 A÷105 ＝K   余23  …  (6)

解方程式(6)，得A = 23 

三      (1)＋(2)－(3)  → (35+21－15) A÷105 ＝ K   余 (70+63－30)  →

41A÷105 ＝ K   余103 …  (7)

解方程式(7)， 便得A = 23  

四   … …

由此可见，不论取何种加减组合方式，结果都一样。为了统一起见，以后一律以各式相

加为准，不必有加有减，便得到一个等效的二元一次不定方程式：(AX－B)÷R＝K 。其中

A是未知数X的系数之和。B是余数之和，R是除数，也是最小公倍数。K是商，它也是未

知数，但只要求是整数而不管它的大小。目的就是求X 而已。

3    现在的问题是，如何解 (AX－B)÷R＝K 这样的不定方程式？

解这个不定方程，归根到底，就是试算，其实就是凑数而已。如

         71A÷105 ＝ K  余163  …  (4)

变为 (71A－163)÷105 ＝ K 后， 求A与K的整数解，

         列表凑罢：

A     71A      (71A－163)        K＝ (71A－163)÷105

               3     213            50                     0.48

               4     284           121                     1.15

               5     355           192                     1.83

               6     426           263                     2.50

              …      …              …                       …

22    1562         1399                    13.32

23    1633         1470                       14         整数了

 

凑到A＝23时，得K＝14，是整数了，就完成。这A＝23就是最小解，通解为：

 A=23＋105 N  ( N=0 1 2 3 … )

当然，也不必非一个不漏的凑，有时可以机巧的少凑一些，直奔目标。但归根到底还是凑。有电脑则可以用电子表格算，那就快多了，但还得要一个个的审视那个K是整数。如果K=5342，你就得从1到5342一、一检视。鼠标滚动也不能太快，总得劳神些罢。

于是我就编了一个VB程序，不必烦劳了。

 

结      语

 

“化为相同除数法”之所以最简易、工作量最小，是因为：

1  组成相同除数的方法，既统一又简单，初中二年级学生都会。

2 “中国剩余定理”，不论“逐级满足法”还是“大衍求一术”，都要解(AX－B)÷R＝K这种不定方程式。而其解法，从根本上说，就是一个字：“凑”。

“化为相同除数法” 解算不定方程  (AX－B)÷R＝K 只“凑”一次，不像“逐级满足法”和“大衍求一术”那样，要 “凑”多次 (N次，即方程的个数)。方程个数越多，“化为相同除数法”就越显得省力。

3  现在一讲“中国剩余定理”，就大讲“大衍求一术”，而很多人既不理解，算起来又麻烦，效果不好。为什么不把通俗易懂的“化为相同除数法”宣传、普及一下呢？

 

我编的VB程序，使用、操作方法是：

1  输入方程个数N。本例 ： N =3

2  再按方程顺序，输入每个方程的除数与余数。本例 ：3  2  5  3  7  2 ↙

3  就得结果：  通解 X＝23＋105 N  ( N ＝ 0 1 2 3 … )

附：中国剩余定理“化为相同除数法”的V B程序

Private Sub Form_Click()                              说          明

Form1.Width = 11520                                    视窗宽

Form1.Height = 15360                                    视窗高

Dim W(20)                                                     W数组  存放除数(模)

Dim R(20)                                                      R数组  存放余数

Dim Y(20)

Dim F(20)

N = InputBox  ("输入方程个数 N =")

For I = 1 To N

    W(I) = InputBox("输入模W(I)=")

R(I) = InputBox("输入余R(I)=")

 Next I

S = 1

For I = 1 To N

   S = S * W(I)                              S是最小公倍数，化归为同一个除数

Next I

A = 0

For I = 1 To N

   Y(I) = S / W(I)                            Y是局部公倍数，是归化后未知数X的系数

A = A + Y(I)                                 A是未知数X的系数之和

Next I

 

B = 0

For I = 1 To N

   F(I) = R(I) * Y(I)                         F是归化后余数

B = B + F(I)                                 B是归化后余数之和

Next I

Print Spc(4); " A= "; A; "   B= "; B

Print

 

For X = 1 To 1000000                       求未知数X，实际上是枚举法求X与K的整数解

  M = (A * X－ B)

   P = M Mod S                                 即 (AX－B)÷S 取余

If P = 0 Then GoTo SS                   求余。余数为0，就是整除。

Next X

SS:

Print Spc(4); " X ="; X                         没有算K，只显示X

 

Print Spc(4); " 通解 X = "; X; " ＋ "; S; " N ( N = 0、1、2、3 … )"

Print Spc(4); " 完"

Print

End Sub