中国剩余定理的基本介绍
在名为《孙子算经》的中国古籍中提到了“水商城”的问题。
今天有不知道那个数的,三三数剩下的2,五五数剩下的3,七七数剩下的2问水学吗?
翻译成白话的话,有一堆东西,三个数字是2个、5个、5个、5个、7个、7个、7个、7个、7个、7个、7个、7个。
这种题目现在经常属于小学算术,但要为难一堆家长。
列出方程来还有可能不会解,却偏偏要求用算术方式。其实主要是因为没找着窍门。可以这么解:
第一个为3除余2的数是5,因此令5+3=8。检查:8为5除余3,为7除余1。
再令8+3×5=23。检查:23为7除刚好余2。
为什么要这么解题呢?这里暂不解释。有兴趣的读者最好自己仔细想一想,想明白了就懂得初等数论四大定理中的中国剩余定理了。这个定理可以说既抽象又直观,所以既可说适宜小学生体会数学乐趣,也适宜难倒博士生不令其骄傲自满。
最后补充一点:事实上任意形式为23+105k(k为非负整数)的自然数都满足要求,其中最小者为23。
(提示:105=3×5×7)
再来看一道叫做“韩信点兵”的数学题:
有兵一队,若列成5行纵队,则末行1人;成6行纵队,则末行5人;成7行纵队,则末行4人;成11纵队,则末行10人,求兵数?
解法一:
第一个为5除余1的数是6,因此令5+6=11。检查:11为6除余5,为7除余4,为11所整除。
于是检查5×6×7=210为11除余1。
于是令11+210×10=2111。
于是所有x=2111+2310k形式的自然数满足要求,2111为其中最小者。
解法二:
令M=5×6×7×11=2310,X=5×6×7=210,Y=5×6×11=330,Z=5×7×11=385,W=6×7×11=462.
210为11除余1,故配以系数a=10;330为7除余1,故配以系数b=4;385为6除余1,故配以系数c=5;462为5除余2,故配以系数d=3;2310配以待定系数k。
有如下算式:aX﹢bY﹢cZ﹢dW﹣kM
=10×210﹢4×330﹢5×385﹢3×462﹣2310k
=6731﹣2310k
易知当k=2时,6731-2310×2=2111为所求最小数。
于是所有x=2111+2310k形式的数均满足要求。
简释:多项式f=aX﹢bY﹢cZ﹢dW﹣kM 当中唯有dW不必是5倍数,若系数d的取值能令dW为5除1,则多项式f必为5除余1。其他情况同理分析。
解法二代表了中国剩余定理的一般性思想,可用之以抽象问题。
这个定理在中国古代很早就有雏形,后来由宋代数学家秦九韶在《数书九章》中给出了一般方法。再后来传到了欧洲,被称为“中国剩余定理”。这个定理的数学思想是极其本质与光辉的,是解所谓丢番图方程的根本思路。接下来本文拟用之以探讨有关孪生素数的问题。
用中国剩余定理去遇上孪生素数
前一节“韩信点兵”题目中我们求得的2111是一个素数,并且2111+2=2113也是一个素数,也就是说(2111,2113)是一对孪生素数。并且很幸运地:2111+2310=4421也是一个素数,而4421+2=4423也是一个素数。于是我们又得到了另一对孪生素数(4421,4423)。
我们继续碰碰运气:4421+2310=6731不是素数,但是6731+2=6733是一个素数。不算糟糕,还是有一半运气。
这现象是纯粹偶然的吗?非也。原题要求所求数为5除余1,为6除余5,为7除余4,为11除余10,则不仅所求x必不为2、3、5、7、11整除,x+2也是必不为2、3、5、7、11整除。这意味着(x+2310k,x+2+2310k)所构成的系列数对中,有较高概率包含孪生素数对。是否必然包含呢?我猜想是的。
我们不妨再随机出一道题试试:
求为6除余5(唯一可选的),为5除余4(余1、2、4三者都是可选的),为7除余6(余1、2、3、4、6五者是可选的),为11除余7(1,2,3,4,5,6,7,8,10)的最小自然数。
解答如下:
令M=2310,X=210,Y=330,Z=385,W=462;
在此:X配以系数a=7;Y配以系数b=6;Z配以系数c=5;W配以系数d=2。
于是:f=aX﹢bY﹢cZ﹢dW﹣kM
=7×210﹢6×330﹢5×385﹢2×462﹣2310k
=1470+1980+1925+924﹣2310k
=6299-2310k
令k=2,则所求的最小自然数x=1679
1679及1681都不是素数,都有大于11的素因子。
但是:1679+2310=3989是素数,而3989+2=3991不是素数;然后,3989+2310=6299以及6299+2=6301都是素数,因此(6299,6301)是孪生素数对。
看来我们用这种办法撞到孪生素数并非偶然。
这种现象对证明孪生素数猜想有没有用呢?很可能是有用的。
中国剩余定理与一种孪生素数猜想的证明思路
标记p(n)为第n个素数。
令M=∏p(i) (i为从1至n),也即:M=2×3×5……×p(n)。
不妨认为有n个数类抽屉,分别标记上2、3、5……p(n)等n个标签记号。
每个抽屉里相应有与记号数字种类相同的多种选择,不妨将这些选择的集合标记为:
定义一
R(p(i))={0,1,2,3,……,P(i)-1}。
实际上,这对应的就是一个简化剩余系。在这样的定义下,就有类似R(11)={0,1,2,3,4,5,6,7,8,10}。
在这当中规定0以及P(i)-2不可选择,其他余数选择则是任意的。
于是,当我们在这n个数类抽屉中,任意从每个数类抽屉中从可选择的余数中各挑一个,然后要求求得一个满足所有以M为模,分别同余于所选的各个余数的最小自然数x(类如上一节的两道题目)。
显然有:x<M,并且x与x+2都不可能为任意一个p(i)≤p(n)所整除。我们不妨将x的取值集合记为:
定义二
X[n]={x | x<M,并且x与x+2都不可能为任意一个p(i)≤p(n)所整除 }
这样的x的数目有多少呢?根据组合规律,易于算得其数目。不妨将该数目标记为K,则:
K=∏(p(i)﹣2) (i从2至n)
=(3-2)×(5-2)×(7-2)×(11-2)×……×(p(n)﹣2)
=1×3×5×9×……×(p(n)﹣2)
也就是说x总计有K种取值情况,在M中的比例为:
K/M = [1×3×5×9×……×(p(n)﹣2)]
÷[2×3×5×7×……×p(n-1)×p(n)]
≥1/2p(n)
其实我们还可以进一步提高精度。为了提高精度我们不妨看看p(14)的例子,此时:
K/M = [1×3×5×9×11×15×17×21×27×29×35×39×41]
÷ [2×3×5×7×11×13×17×19×23×29×31×37×41×43]
=[1/(2×43)]×[(9×15×21×27×35×39)/(7×13×19×23×31×37)]
其中:[(9×15×21×27×35×39)/(7×13×19×23×31×37)=104483925/45612749>2
由此可见,前式中的常数2在p(n)足够大时是可消除的,也就是说当p(n)足够大时 K/M>1/p(n)。
于是有如下定理:
定理一
在全体自然数中,将属于X[n]集合中的数的比例记为λ,于是λ=K/M>1/2p(n)。因为X[n]集合中的数在自然数中的分布是以M为周期的,自然数区间[1,M]、[1+M,2M]以及[1+kM,(k+1)M]关于X[n]集合数的分布是完全同构的。从而,任意连续M个数,譬如[y,y-1+M]中属于X[n]集合数的比例也是λ=K/M。
我们也不难知道:
定理二
如果自然数x∈X[n],并且p(n)<x<x+2<p(n+1)²,(x,x+2)必是孪生素数。
理由很简单:所有小于p(n+1)²的数,如果是一个合数必有素因子不大于p(n);因此,没有不大于p(n)的素因子并且又小于p(n+1)²的数要么是1要么是素数。
因此如果我们能够证明自然数区间(p(n),p(n+1)²)中必然存在X(n)集合数,我们就可以证明(p(n),p(n+1)²)区间中必然存在孪生素数。