巴马腕表批发销售联盟

(六上)同步奥数:中国剩馀定理

慈爱老师原创号2019-09-22 08:40:14

中国剩余定理



一元线性同余方程组问题最早可见于中国南北朝时期(公元5世纪)的数学著作孙子算经》卷下第二十六题,叫做“物不知数”问题,原文如下:


有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何?


即,一个整数除以三余二,除以五余三,除以七余二,求这个整数。《孙子算经》中首次提到了同余方程组问题,以及以上具体问题的解法,因此在中文数学文献中也会将中国剩余定理称为孙子定理。


宋朝数学家秦九韶于1247年《数书九章》卷一、二《大衍类》对“物不知数”问题做出了完整系统的解答。明朝数学家程大位将解法编成易于上口的《孙子歌诀》:


三人同行七十希,五树梅花廿一支,七子团圆正半月,除百零五使得知

这个歌诀给出了模数为3、5、7时候的同余方程的秦九韶解法。意思是:将除以3得到的余数乘以70,将除以5得到的余数乘以21,将除以7得到的余数乘以15,全部加起来后除以105,得到的余数就是答案。比如说在以上的物不知数问题里面,按歌诀求出的结果就是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,


若避开难点,换个角度看,那么解这组方程,不一定非用“同余式方程组”的解法。


就我所知,有五个方法:

一、枚举法

二、解不定方程法

三、逐级满足法

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

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


 现将陈景润所著《初等数论Ⅰ》中的一个习题为例,用五种方法解算,可以对比。


试解下列同余方程

X2(mod7 )

X5(mod9 )

X1(mod5 )X

 一 枚举法

X≡2(mod7 )X÷7=A…2X=7A+2

X≡5(mod9 )相当于X÷9=B…5X=9B+5

X≡1(mod5 )X÷5=C…1X=5C+1

枚举法就是按A=0、1、2、3、4…B=0、1、2、3、4…C=0、1、2、3、4…

代入各式,计算各式的X,当三个X相同时,就是一个解。

A、B、C1234 … 9101112 …1617 18…

XA 91623 30…65727986

XB1423 32 41 …86 …

XC1611 1621 … 46515661 …8186 …

即,当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全是整数时,才合格。结果如下:

ABC

324.4

12917

2116 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+315KX=86、通解为X=86+315K。实际上,这仍然是枚举法,只是枚举个数减少一些而已。


 逐级满足法

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


P要同时考虑两个方程的倍数关系如7A9B,又要考虑两个余数关系,如余2、余5,方程数一多,处理时要拐几个弯,方法不易理解。


最近,我在作《数论—余数习题集》时,对“逐级满足法”作了改进。把第一个方程的通解,直接作为第二个方程的初值,不作任何转弯,就同时解决了两个方程之间的相关关系及余数关系,变得容易理解,容易操作、便于列式。这可以说是我的又一个心得罢。


仍按原例: X除以72、除以95、除以51,求最小X


答:最小X=86通解 X =86 315 N ( N=12 )


已知:

X2(mod7 )X÷7=A2X=7A2

X5(mod9 )相当于 X÷9=B5 X=9B5

X1(mod5 )X÷5=C1X=5C1

ABC都是整数,可用K统一表示,且不论其具体数值。


解算步骤:


1 先解第一个方程X÷72的通解X1。一般都很容易,即:

通解X1=余数+除数的倍数,例中X1=27A 。其中余数就是最小解X0=2,加上7的最小公倍数的A倍,就是通解X1=27A 


X1是一个数列,其中总有一个数能满足所有方程,关键在于A是多少,又怎样定?A怎样定呢?现在不能定。因为要考虑到它能满足第二个方程,所以到那时才能定下来。

2、第二个方程。X÷95,此时的X首先应满足本方程要求: (X5)÷9 = K(K是整数)。但同时又要满足第一个方程,既然X1可以满足所有方程,所以就干脆用第一方程的通解X1代替第二方程的未知数X ,即用(X1)取代X。即应满足 (X15)÷9 = K,才顾及了两式。


注意,(X15)÷9 =K这种形式的方程,是有规律的,即:

(第一方程的通解X1=27A   第二方程的余数5 )÷第二方程的除数9=整数K且以下各方程也都是这样的规律,亦即:

( 上一个方程的通解  本方程的余数 )÷本方程的除数   整数K

现在有了 (27A5)÷9 =K ,就整理为(7A3)÷9 = K。这时两个余数就自动合并了。


解此 (7A3)÷9 = K方程,便得A=3  K2


于是 X1=27A=27×3=23。此时,就把X123作为第二个方程的最小解,转为X2,即X223。再加上79的最小公倍数7×9=63的倍数,得通解X22363M。这个X2,既满足第一个方程又满足第二个方程。


X2也是一个数列,其中总有一个数,能满足所有方程,所以就是下一个方程的未知数初值了。关键在于M是多少。M怎样定呢?现在不能定。要考虑到它能满足第三个方程。到那时才能定下来。


至此,得到一个同余式 X223(mod63 ),实际上它是

X2(mod7 )

X5(mod9 )二个同余式的共同解。

至于用什么方法来解 (7A3)÷9 = K 这个二元一次不定方程呢?(7A3)÷9 = K也就是7A9K = 3在陈景润所著《初等数论Ⅰ》中,有一个手算方法,先用“辗转相除法”得到各次余数,直到余数为“ ,再反求出满足余数“ 1 时的XK的新系数,再通过“同余式”的转换,转换成己知余数(如本例的3),才得到最终的X的系数A。整个过程步骤多。反求XK的新系数时、转换成己知余数时,都颇费工夫,我见了生畏。还不如老老实实的试算、凑数。

(7A3)÷9 = K AK的整数解,

 列表凑罢:

A7A(7A3)K (7A3)÷9

003 0.33

1740.44

321182好了,K是整数了

4  不必算了。


A3K。其实K仅起检验作用,是整数就行了,没有其他用处。


解二元一次不定方程最好的方法,当然是编个电脑程序。我已经编就了,请用吧


3、第三个方程。X÷51,此时X首先应满足本方程要求: (X1)÷5 = K,又要满足第一、第二个方程。既然X2可以满足所有方程,所以就干脆用第二方程的通解X2代替第三方程的未知数X ,即用(X2)取代X。即应满足:

(X21)÷5 = (2363M 1)÷5=K,→ (63M22)÷5 = K才顾及了三个方程。


解此元不定方程 M=1  K17。把M代入X2


于是 X2=2363M=2363×1=86,就把X286作为第三个方程的最小解,转为X3

X386。再加上635的最小公倍数63×5=315的倍数,得通解

X386315P(P=123  )

验算 86÷7 =12 2

86÷9 = 9 5

86÷5=17 1

*****

“逐级满足法”解法有规律了,容易操作了。但也有两点麻烦


1组成形如 (AX±B)÷CK的不定方程,要一个个顺序进行,虽有规律,但还是比较麻烦。

2、解算(AX±B)÷CK方程,求待定量XK,无论用手算,或是电子表格算,要解(N1)次。也很烦人,特别是大数相除更麻烦。

为了加快计算,我编了一个VB程序,不用烦心,输入完数据,↙,就出结果了。

上述算题:

输入方程个数N = 3

输入各方程的除数与余数 729551

结果为:

通解 X =86 315 N ( N=12 )

还有一例:我曾靠电子表格算了一天,才得结果的,现在包括输入在内,仅15秒就搞定。

输入方程个数N = 6

输入各方程的除数与余数 32537211913743

结果为:

通解 X =20183 60060N ( N=12 )


四、化为相同除数 法

X2(mod7 )

X5(mod9 )

X1(mod5 )

这三个同余式,除数不同,分别为795,为了能利用同余式的和差特性,简化计算,先设法使它们的除数相同,为此:

X2(mod7 )两边都乘9*5,得X*452*45(mod 7*45 )45 X90(mod 315 ) (1)

X5(mod9 ) 两边都乘7*5,得X*355*35(mod 9*35 )35 X175(mod 315 ) (2)

X1(mod5 ) 两边都乘7*9,得X*631*63(mod 9*63 )63 X 63(mod 315 ) (3)

(1)(2)(3) (4) 143 X328(mod 315 ) 4)

根据同余式的加减性质,(1)(2)(3)得:

143 X328(mod 315 ) 143 X13(mod 315 ),化为带余除式为:

143 X÷315=K 13亦即 143X13=315 K ,有(143X13)÷315K(整数)

(143X13)÷315K(整数)用通式表示为 (AXB)÷SK

解得 X=86K=38(实际上不用它,在此仅确认它是整数就行了)

通解为 X86+315 N( N 12 )

 X86(mod 315 )


数论是纯粹数学的分支之一,主要研究整数的性质。


按研究方法来看,数论大致可分为初等数论和高等数论。初等数论是用初等方法研究的数论,它的研究方法本质上说,就是利用整数环的整除性质,主要包括整除理论、同余理论、连分数理论。高等数论则包括了更为深刻的数学研究工具。它大致包括代数数论、解析数论、计算数论等等。


初等数论主要就是研究整数环的整除理论及同余理论。此外它也包括了连分数理论和少许不定方程的问题。本质上说,初等数论的研究手段局限在整除性质上。


初等数论中经典的结论包括算术基本定理、欧几里得的质数无限证明、中国剩余定理、欧拉定理(其特例是费马小定理)、高斯的二次互反律, 勾股方程的商高定理、佩尔方程的连分数求解法等等



Copyright © 巴马腕表批发销售联盟@2017