admin 中国剩余定理的基本介绍
在名为《孙子算经》的中国古籍中提到了“水商城”的问题。
今天有不知道那个数的，三三数剩下的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)²）区间中必然存在孪生素数。