中国剩余定理的五种解法

一、枚举法
二、解不定方程法
三、逐级满足法
四、化为相同除数的同余式法、
五、才用到典经的、不同除数的同余式组解法
现将陈景润所著《初等数论Ⅰ》中的一个习题为例,用五种方法解算,可以对比。
试解下列同余方程
X≡2  (mod  7 )
X≡5  (mod  9 )
X≡1  (mod  5 )      求X

一、 枚举法
X≡2  (mod  7 )           X÷7=A…2        X=7A+2
X≡5  (mod  9 )   相当于  X÷9=B…5   →   X=9B+5
X≡1  (mod  5 )           X÷5=C…1        X=5C+1
枚举法就是按A=0、1、2、3、4…    B=0、1、2、3、4…   C=0、1、2、3、4…
代入各式,计算各式的X,当三个X相同时,就是一个解。
A、B、C    0    1    2    3    4 …  9    10    11    12 …   16   17   18…
XA          2    9    16   23   30…  65   72    79    86…
XB        5   14    23   32   41 … 86 …
XC      1    6    11   16   21 … 46   51    56    61 …    81   86  …
即,当A=12、B=9、C=17时,X 都等于86。所以最小 X=86。由于7、9、5的最小公倍数是315,所以,通解   X=86+315K  (K=0、1、2、3、…)
枚举法就是凑,很'笨’,但也最直观。适合小学生学习。也可用电子表格计算,那太快捷了。

二、 解不定方程法
X=7A+2
X=9B+5     →9B+5=7A+2    →9B=7A+2-5=7A-3    →B=(7A-3)/9
X=5C+1     →5C+1=7A+2   →5C=7A+2-1=7A+1    →C=(7A+1)/5
由B=(7A-3)/9,算得:当A=3时,B=2,但A=3时,C=(7A+)/5=4.4。由于A、B、C只能是整数。所以 3、2、4.4这一组,不符合要求,要重算A。又由于B=(7A-3)/9的分母是9,所以下一个A,只能在3的基础上,增加一个9的倍数,所以A只能取12、21、30、39…有了A,再算B、C,当A、B、C全是整数时,才合格。结果如下:
A       B        C
3       2        4.4
12      9       17
21     16       29.6

可见,只能取A=12 、B=9  、C=17 , 代入原式:
X=7A+2=7*12+2=86
X=9B+5=9*9+5=86
X=5C+1=5*17+1=86
得 X=86、通解为X=86+315K得X=86、通解为X=86+315K。实际上,这仍然是枚举法,只是枚举个数减少一些而已。

三、逐级满足法
这个方法的基本思路是:先解算出合符第一个方程的X1。再解算出合符第一、第二个方程的X2,令X2=X1+P1。关键是P1要保持第一个方程中的倍数要求,又要合符第二个方程中的剩余要求。再解算出合符第一、第二、第三个方程的X3,令X3=X2+P2,关键是P2要保持第一第二两个方程中的倍数要求,又要合符第三个方程中的剩余要求。这样逐级解算,满足全部条件。
P要同时考虑两个方程的倍数关系如7A、9B,又要考虑两个余数关系,如余2、余5,方程数一多,处理时要拐几个弯,方法不易理解。
最近,我在作《数论—余数习题集》时,对“逐级满足法”作了改进。把第一个方程的通解,直接作为第二个方程的初值,不作任何转弯,就同时解决了两个方程之间的相关关系及余数关系,变得容易理解,容易操作、便于列式。这可以说是我的又一个心得罢。
仍按原例: X除以7余2、除以9余5、除以5余1,求最小X。
答:最小X=86  通解 X =86 +315 N ( N=1、2、3 … )
已知:
X≡2  (mod  7 )           X÷7=A…2         X=7A+2
X≡5  (mod  9 )   相当于  X÷9=B…5   →    X=9B+5
X≡1  (mod  5 )           X÷5=C…1         X=5C+1
A、B、C都是整数,可用K统一表示,且不论其具体数值。
解算步骤:
1、 先解第一个方程X÷7余2的通解X1。一般都很容易,即:
通解X1=余数+除数的倍数,例中X1=2+7A 。其中余数就是最小解X0=2,加上7的最小公倍数的A倍,就是通解X1=2+7A 。
X1是一个数列,其中总有一个数能满足所有方程,关键在于A是多少,又怎样定?A怎样定呢?现在不能定。因为要考虑到它能满足第二个方程,所以到那时才能定下来。
2、第二个方程。X÷9余5,此时的X首先应满足本方程要求: (X-5)÷9 = K  (K是整数)。但同时又要满足第一个方程,既然X1可以满足所有方程,所以就干脆用第一方程的通解X1代替第二方程的未知数X ,即用(X1)取代X。即应满足 (X1-5)÷9 = K,才顾及了两式。
注意,(X1-5)÷9 =K这种形式的方程,是有规律的,即:
(第一方程的通解X1(=2+7A ) 减  第二方程的余数5 )÷第二方程的除数9=整数K,
且以下各方程也都是这样的规律,亦即:
( 上一个方程的通解 减 本方程的余数 )÷本方程的除数 应 = 整数K
现在有了 (2+7A-5)÷9 =K ,就整理为(7A-3)÷9 = K。这时两个余数就自动合并了。
解此 (7A-3)÷9 = K方程,便得A=3 、 K=2。
于是  X1=2+7A=2+7×3=23。此时,就把X1=23作为第二个方程的最小解,转为X2,即X2=23。再加上7与9的最小公倍数7×9=63的倍数,得通解X2=23+63M。这个X2,既满足第一个方程又满足第二个方程。
X2也是一个数列,其中总有一个数,能满足所有方程,所以就是下一个方程的未知数初值了。关键在于M是多少。M怎样定呢?现在不能定。要考虑到它能满足第三个方程。到那时才能定下来。
至此,得到一个同余式  X2≡23  (mod  63 ),实际上它是
X≡2  (mod  7 )
X≡5  (mod  9 )   二个同余式的共同解。
至于用什么方法来解  (7A-3)÷9 = K  这个二元一次不定方程呢?(7A-3)÷9 = K也就是7A-9K = 3,在陈景润所著《初等数论Ⅰ》中,有一个手算方法,先用“辗转相除法”得到各次余数,直到余数为“ 1 ”,再反求出满足余数“ 1 ”时的X、K的新系数,再通过“同余式”的转换,转换成己知余数(如本例的3),才得到最终的X的系数A。整个过程步骤多。反求X、K的新系数时、转换成己知余数时,都颇费工夫,我见了生畏。还不如老老实实的试算、凑数。
(7A-3)÷9 = K   求A与K的整数解,
列表凑罢:
A     7A     (7A-3)     K= (7A-3)÷9
0      0       -3         - 0.33
1      7         4            0.44
3     21        18            2        好了,K是整数了
4     … … 不必算了。
得A=3、K=2 。其实K仅起检验作用,是整数就行了,没有其他用处。
解二元一次不定方程最好的方法,当然是编个电脑程序。我已经编就了,请用吧
3、第三个方程。X÷5余1,此时X首先应满足本方程要求: (X-1)÷5 = K,又要满足第一、第二个方程。既然X2可以满足所有方程,所以就干脆用第二方程的通解X2代替第三方程的未知数X  ,即用(X2)取代X。即应满足:
(X2-1)÷5 = (23+63M -1)÷5=K,→ (63M+22)÷5 = K。才顾及了三个方程。
解此二元不定方程 M=1 、 K=17。把M代入X2,
于是  X2=23+63M=23+63×1=86,就把X2=86作为第三个方程的最小解,转为X3
即X3=86。再加上63与5的最小公倍数63×5=315的倍数,得通解
X3=86+315P。(P=1、2、3 … )
验算  86÷7 =12   … 2
86÷9 = 9   … 5
86÷5=17   … 1
*   *   *   *   *
“逐级满足法”解法有规律了,容易操作了。但也有两点麻烦:
1、组成形如 (AX±B)÷C=K的不定方程,要一个个顺序进行,虽有规律,但还是比较麻烦。
2、解算(AX±B)÷C=K方程,求待定量X、K,无论用手算,或是电子表格算,要解(N-1)次。也很烦人,特别是大数相除更麻烦。
为了加快计算,我编了一个VB程序,不用烦心,输入完数据,↙,就出结果了。
上述算题:
输入方程个数N = 3
输入各方程的除数与余数  7   2   9   5   5   1  ↙
结果为:
通解 X =86+ 315 N ( N=1、2、3 … )
还有一例:我曾靠电子表格算了一天,才得结果的,现在包括输入在内,仅15秒就搞定。
输入方程个数N = 6
输入各方程的除数与余数  3  2  5  3  7  2  11  9  13  7  4  3  ↙
结果为:
通解 X =20183+ 60060N ( N=1、2、3 … )

四 、化为相同除数法
X≡2  (mod  7 )
X≡5  (mod  9 )
X≡1  (mod  5 )
这三个同余式,除数不同,分别为7、9、5,为了能利用同余式的和差特性,简化计算,先设法使它们的除数相同,为此:
X≡2  (mod  7 )两边都乘9*5,得X*45≡2*45  (mod 7*45 )  →45 X≡90   (mod 315 ) …(1)
X≡5  (mod  9 ) 两边都乘7*5,得X*35≡5*35  (mod 9*35 )  →35 X≡175  (mod 315 ) …(2)
X≡1  (mod  5 ) 两边都乘7*9,得X*63≡1*63  (mod 9*63 )  →63 X≡ 63  (mod 315 ) …(3)
(1)+(2)+(3)= (4)  →   143 X≡328   (mod 315 ) …4)
根据同余式的加减性质,(1)+(2)+(3)得:
143 X≡328   (mod 315 )  即 143 X≡13  (mod 315 ),化为带余除式为:
143 X÷315=K …13  亦即   143X-13=315 K ,有(143X-13)÷315=K(整数)
(143X-13)÷315=K(整数)用通式表示为  (AX-B)÷S=K
解得  X=86、K=38  (实际上不用它,在此仅确认它是整数就行了),
通解为    X=86+315 N  ( N=  1、2、3 … )
或   X≡86  (mod 315 )
这一种算法,在所有五种算法中,我认为是最简洁、工作量最小的算法。因为不管方程有多少个,它解算形如(AX-B)÷S=K这种不定方程,仅解一次而已。而其他方法要解多次。同时,这种算法也容易理解,算法单纯。

五、 典经的、“大衍求一术”解法
X≡R1  (mod  m1 )     X≡2  (mod  7 )
X≡R2  (mod  m2)      X≡5  (mod  9 )
X≡R3  (mod  m3)      X≡1  (mod  5 )
名词注释及计算步骤:
1  余数R:、R1=2、R2=5、R3=1
2  模,亦即除数m:例中m1=7、m2=9、m3=5
3  模的最小公倍数G:G=m1*m2*m3,例中M=7*9*5=315
4  衍数(局部公倍数)y:Y1=m2m3、Y2=m1m3,Y3=m1m2,例中Y1=9*5=45、Y2=7*5=35、Y3=7*9=63
5  乘率C:这是解算中国剩余定理的关键,而计算“乘率”的方法,是秦九韶在《数书九章》一书中首次提出的,称之为“大衍求一术”。“求一”就是使(衍数*乘率)除以模(除数),而余数为1。即:
衍数Y*乘率C≡1  (mod  m),乘率C可以经过反算而得到。例中Y1C1≡1  (mod  7 )、
Y2C2≡1  (mod  9 ) 、Y3C3≡1  (mod  5 )。
计算C1方法。由Y1C1≡1  (mod  7 ), →45C1≡1  (mod  7 )  →(45C1-1)  /  7=整数N ,得C1=5。因为45*5=225,225-1=224,224÷7=32,32是整数,合符要求。C2、C3之计算也相仿。乘率C之计算见下表:
同余式 i
衍数Y
乘率C
余1
模m
检验  (Y*C-1)/m  = 整数
1
45
5
1
7
(45*C-1)/7 =N   (45*5-1)/7 =  32
2
35
8
1
9
(35*C-1)/9 =N  (35*8-1)/9 =  31
3
63
2
1
5
(63*C-1)/5 =N  (63*2-1)/5 =  25
最终结果,X≡R1Y1C 1+R2Y2C2+R3Y3C3(mod G)
即X≡Σ余数*衍数*乘率 (mod G),见下表计算:
i
余数R
衍数Y
乘率C
R*Y*C
1
2
45
5
450
2
5
35
8
1400
3
1
63
2
126
Σ
1976
X≡1976  (mod 315)
1976 除去315的6倍后,剩下86,最终,X≡86  (mod 315)
“大衍求一术”的关键与难点,是如何解“衍数Y*乘率C≡1  (mod  m)”,得乘率C。也就是解算方程(Y*C-1)/m =N 。
2015-11-21补充:
X≡R1  (mod  m1 ) → X≡2  (mod  7 )  ×5×9 →   45 X≡90  (mod  315 )
X≡R2  (mod  m2)  →  X≡5  (mod  9 )  ×7×5 →   35 X≡175  (mod  315)
X≡R3  (mod  m3)  →  X≡1  (mod  5 )  ×7×9 →   63 X≡63  (mod  315 )
→   45 C1≡1  (mod  7 )  →   (45 C1 -1 ) ÷7 =整数 → C1 =5
→   35 C2≡1  (mod  9)   →   (35 C2 -1 ) ÷9 =整数 → C2 =8
→   63 C3≡1  (mod  5 )  →   (63 C3 -1 ) ÷5 =整数 → C3 =2

六、  评  论
1 、综合上述五种解法,归根到底,关键点,也是难点,就是都要解“(AX+B)÷C= K”这种类型不定方程。而解这种不定方程的方法,既没有公式又没有窍门,归根到底还是一个“凑”字了。其中“枚举法”是小学生都懂的凑数法。因此可以说,中国剩余定理其实并不神秘,就是一个如何凑数的问题。
2 、五种解法中我认为“化为相同除数法”最简易、工作量最小。因为:
第一,它要使除数相同,方法最简单、统一,初中二年级学生都会。
第二,它解算不定方程“(AX+B)÷C= K” 只解一次,也即只“凑”一次。而“逐级满足法”和“大衍求一术”,则要“凑”多次 (N次,即方程的个数)。方程个数越多,“化为相同除数法”就越显得省力。我认为应该宣传、普及一下通俗易懂的“化为相同除数”。
3、至于说到“大衍求一术”的同余式“衍数Y*乘率C≡1  (mod  m)”是怎样来的,又为什么成为解题的关键,在陈景润所著《初等数论Ⅰ》1978年版85页上有理论推证。这应该是一个现代数学的推证,而不是在论证秦九韶的理论就是这样的。也就是说,这是殊途同归。至于秦九韶到底是怎样想的,或许他有更容易为常人所理解的机理,那就不得而知了,于是我们钦佩古代数学家的智慧。我们钦佩古代数学家的智慧,但不一定非要走他的路,固守他的方法。有了更好的方法,应该学习推广。至于以后是不是有更好的解法,那谁又知道呢。

(0)

相关推荐