中国剩余定理即孙子定理的五种解法

怼烎@ 2022-08-09 13:47 435阅读 0赞

加深一下理解，找了点纯数学的资料（老者善学，尤老骥伏枥，况乎我也）：  
“中国剩余定理”是公元5-6世纪、我国南北朝时期的一部著名算术著作《孙子算经》中的一个“物不知数”的解法问题：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？答曰：二十三。

《孙子算经》中虽然也有计算方法的叙述，如术曰：「三三数之剩二，置一百四十，五五数之剩三，置六十三，七七数之剩二，置三十，并之，得二百三十三，以二百一十减之， 即得。凡三三数之剩一，则置七十，五五数之剩一，则置二十一，七七数之剩一，则置十五，即得。」但也仅仅知道140+63+30=233、 233-210=23，得物数23。至于接着说的剩一、置70、置21、置15，应该是说140=70\*2、63=21\*3、30=15\*2的来源，而 2、3、2又正是剩余数、210又正是除数3、5、7的最小公倍数的2倍。综合之，解的算式为70\*2+21\*3+15\*2－2\*3\*5\*7=23。虽然 如此，但仍不知为什么要这么算，还有， 70、21、15是怎样来的？等等，如读天书。如果换一个题目你能算吗？连照搬都没法搬。

这个问题，过了八、九百年，到了宋代，才有秦九韶在《算书九章》中给以解答。但现代人读古代数书，正如读古代医书一样，绝大多数是丈二和尚模不着头了。

“中国剩余定理”的现代数学提法是，解一元一次同余式方程组：

X≡2  (mod 3)

X≡3  (mod 5)

X≡2  (mod 7)

初等数论中有解法，得X最小值为23，通解为X=23 + 105K。但因为原理很难理解，所以也只能按公式规定的步骤与方法，依样画葫芦的计算罢了。时间一长也就忘光了。由此可见，“中国剩余定理”的理论及计算方法，还达不到普知的地步，不像一元二次方程的公式，初中生都知道公式怎样来的，怎样应用的。

若要问我：你对“中国剩余定理”的态度是怎样的呢？回答只有两个字：“敬畏”。

其实“中国剩余定理”，就是解一组带余除法的不定方程：

X÷3=A…2

X÷5=B…3

X÷7=C…2，

若避开难点，换个角度看，那么解这组方程，不一定非用“同余式方程组”的解法。就我所知，有五个方法：

一、枚举法

二、解不定方程法

三、逐级满足法

四、化为相同除数的同余式法、

五、才用到典经的、不同除数的同余式组解法

现将陈景润所著《初等数论Ⅰ》中的一个习题为例，分而习之。

试解

X≡2  (mod  7 )

X≡5  (mod  9 )

X≡1  (mod  5 )

一 枚举法

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

三  逐级满足法

这个方法的基本思路是：先解算出合符第一个方程的X1。再解算出合符第一、第二个方程的X2，令X2=X1\+P1。关键是P1要保持第一个方程中的倍数要求，又要合符第二个方程中的剩余要求。再解算出合符第一、第二、第三个方程的X3，令X3=X2\+P2，关键是P2要保持第一第二两个方程中的倍数要求，又要合符第三个方程中的剩余要求。这样逐级解算，满足全部条件。

这使我想起老本行测量，好比测量平差的分组平差。只是测量分组平差时，要改化方程式的系数，比较麻烦，而这里仅要调整倍数与余数就行了。

X=7A+2

X=9B+5

X=5C+1

先解第一方程  X=7A+2。最简，X1=2。

再解第二方程  X=9B+5 。令X2=X1+P1=2+P1。首先要求P1应是7的倍数7K，即P1只能=7、14、21、27…为什么呢，因为第一个方程X=7A+2中，有**7A**一项，所以X2最起码应是X2==X1\+P1=2+P1=2+7K，即应是 9、16、23、30、…中的一个，才能满足第一个方程中的7倍数的要求。

但仅仅这样取P1，不一定满足第二个方程中的剩余5的要求。为此，要统一考虑第一第二方程的总的剩余要求。要将X1=2看作是第一第二两个方程的总的余数的一部份。现在要求剩余为5，而前面已经有余数2了，所以P1除以9后，余数应为5－2=3，才能使总余数为5。这样才满足第二个方程中的剩余5的要求。

总之，P1应是7的倍数、且P1÷9余3，这就是对P1的要求。

用方程表示为：7K÷9=N…3，或(7K－3)/9=整数N。

将K=1、2、3、4…代入，K=1时，N=0.44，非整数，不合符要求。再往下算，得K=3时，N=2，整数了，合符要求。所以P1=7K =7\*3=21。这样，X2=X1\+P1=2+21=23

注：请回头看看枚举法，当A=2、B=3时，也得XA=XB=23，凑两个方程容易。凑三个以上就难了。

再解第三方程  X=5C+1，前已得X2=23。

令X3=X2\+P2=23+ P2。首先要求P2应是7\*9=63的倍数63K，即P2只能=63、126、189…为什么呢，因为第一第二方程中有**7A**、9B，63是它们的最小公倍数。

同样，P2不一定满足第三个方程中的剩余1的要求。为此，要统一考虑第一第二第三方程的总的剩余要求。要将X2=23看作是第一第二第三方程的总的余数的一部份。现在要求剩余1，而前面已经有余数23了，所以P2除以5后，余数应为1－23=－22，这样才满足第三个方程中的剩余1的要求。但余数=－22不是很怪吗？实际上不怪，因为在数论中，不管除数的大小，可以把除数归入余数之中的。例如83÷5=16…3，可以表示为 83÷5=15…8，也可以表示为 83÷5=21…… －22，它们用同余表示为 83 ≡3 (mod  5 ) 、83 ≡8 (mod 5 ) 、83 ≡－22 (mod  5 )，是相同的。现在第三式中除数是5，现要求余数为－22，便可以改化为5\*5－22=25－22=3，即余3。

这样，P2应是63的倍数、且P1÷5余3，这就是对P2的要求。

用方程表示为：63K÷5=N…3，或(63K－3)/5=整数N。

将K=1、2、3、4…代入，可得K=1时，N=12，合符要求。所以P2=63\*1=63，即X3=X2\+P2=23+63=86，这是最小解。通解为X=86+315K

四 化为相同除数的同余式法

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)得：

(45-35) X≡(90-175)  (mod 315 )   →10 X≡－85  (mod 315 )  →10 X≡230  (mod 315 )

而10 X≡230  (mod 315 )就意味着(10X－230)÷315=商N (整数)，由此解得X=86、N=2，合符整数要求，所以 X≡86  (mod 315 )

验算：X≡86  (mod 315 ) ，两边都乘63，得 63 \*X≡86\*63  (mod 315 )

→63 X≡5418  (mod 315 )  →63 X≡63  (mod 315 )正与(3)相同。没有算错。

所以  X=86是最小解。通解为  X=86+315K或X≡86  (mod 315 )

五 典经的、不同除数的同余式组解法

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之计算见下表：

6  最终结果，X≡R1Y1C 1\+R2Y2C2\+R3Y3C3  (mod G)

即X≡Σ余数\*衍数\*乘率 (mod G)，见下表计算：

X≡1976  (mod 315) 。1976 除去315的6倍后，剩下86，最终，

X≡86  (mod 315)

六 用分组的逐级满足法解“韩信点兵”

陈景润 著《初等数论Ⅰ》例：

韩信点兵：有兵一队，若列成5行纵队，则末行1人。成6行纵队，则末行5人，成7行纵队，则末行4人，成11行纵队，则末行10人。求兵数。

设：X是兵数，依题意有：

X≡1  (mod 5)

X≡5  (mod 6)

X≡4  (mod 7)

X≡10 (mod11)

现将四式分为两大组，对每组的两个式，都用逐级满足法，分别求出两个X。再合并求出最终X。这是我独自想出的方法，正确性、简便性如何，请一试验证之。

第一组：

X≡1  (mod 5)  →       X1=1

X≡5  (mod 6)  →      X2= X1\+P1=1+P1  →P1=5K。

关于余数，前已有1，现要求余5，则应余5－1=4，所以P1又应满足(5K－4)/6=整数N的要求。经电子表格凑算，当K=2时，N=1，行。这样，X2=1+5K=1+5\*2=11，此两式最小公倍数5\*6=30，所以 有X≡11  (mod 30) …(A)

第二组：

X≡4  (mod 7)  →       X3=4

X≡10  (mod 11)  →     X4=X3\+P3=4+P3  →P3=7K。

关于余数，前已有4，现要求余10，则应余10－4=6，所以P3又应满足(7K－6)/11=整数N的要求。经电子表格凑算，当K=4时，N=2，行。这样，X4=4+7K=4+7\*4=32，此两式最小公倍数7\*11=77，所以 有

X≡32  (mod  77) ……(B)

经分批解算，得到两个新的同余式：

X≡11  (mod  30) ……(A)

X≡32  (mod  77) ……(B)

再用逐级满足法解。XA=11、XB=XA\+PA=11+PA、PA=30K。

关于余数，前已有11，现要求余32，则应余32－11=21，所以PA又应满足(30K－21)/32=整数N的要求。经电子表格凑算，当K=70时，N=27，行。这样，XB=11+30K=11+30\*70=2111，此两式最小公倍数30\*77=2310，所以有：

X≡2111  (mod 2310) ，即X=2111+2310K

现再用第四节“化为相同除数的同余式法”来解算这两个新的同余式。

X≡11  (mod  30) ……(A)，乘77，得 77X≡847  (mod  2310)……(1)

X≡32  (mod  77) ……(B)，乘30，得 30X≡960  (mod  2310)……(2)

(1)－ (2) ，得 47X≡－113  (mod  2310) ……(3)，相当于要求(47X+113)/2310=N整数。由电子表格帮忙，算得X=2111，此时N=43，合符要求。所以也得到  X=2111+2310K。

真是路路通啊，有收获。

七   写后感

2013年的国庆过得很忙，甚至还起了一个早床。感谢我的老伴，以她的勤劳与宽容，给了我闲暇与自由，使我能够安逸地做做算术、写写文章，自得其乐，有时间消磨我的时光。

我仰望深邃的数学天空，深感自己的渺小。我浅尝一滴数学的清泉，来润湿一下我干枯的灵感。

原文：[http://blog.sina.com.cn/s/blog\_a6f9a3b60101favb.html][http_blog.sina.com.cn_s_blog_a6f9a3b60101favb.html]

[http_blog.sina.com.cn_s_blog_a6f9a3b60101favb.html]: http://blog.sina.com.cn/s/blog_a6f9a3b60101favb.html

中国剩余定理即孙子定理的五种解法

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关中国剩余定理及同余方程解法（这里同余方程属于一种情况，剩余定理属于一种解法）

相关中国剩余定理即孙子定理的五种解法

相关（ACM数论）中国剩余定理（孙子定理）

相关中国剩余定理的应用

相关中国剩余定理

相关中国剩余定理（孙子定理）

相关中国剩余定理

相关算法——中国剩余定理（孙子定理）

相关中国剩余定理

相关中国剩余定理-CRT