• 汇集公众科学智慧交流科学思想见解
  • 点燃科学智慧火花构建互动交流平台
科学智慧火花
发表评论  45                

利用抽屉原理证明素数无穷多

投稿时间:2015-01-25 10:05 投稿人:王晓明 【字号: 访问量:

素数无穷多有十几种方法证明,现在我再利用抽屉原理提供一种新的证明方法。分为三个板块,第一第二板块后面提供已经有结论参考资料。

第一、素数的公式

公元前300年古希腊的埃拉托斯特尼创造了一种筛法,可以产生任意大的数以内的全部素数: 要得到不大于某个自然数n的所有素数,只要在2—n中将不大于素数的倍数全部划去即可。

上述筛法可以总结为

1,如果n是合数,则它有一个因子d满足1<d≤

2,若自然数n是一个素数,当且仅当它不能被不大于任何素数整除,则n是一个素数。)。

可以把2的汉字内容等价转换成为英语字母:

.........(1)

其中 表示顺序素数2,3,5,....。≠0。

这样解得的n,若,则n是一个素数。

我们可以把(1)式内容等价转换同余式组表示:

..........(2)

由于(2)的模,,..., 都是素数,因此两两互素,根据孙子定理(中国剩余定理)知,对于给定的,,...,,(2)式在...范围内有唯一解。

范例

例如: k=1时,,解得n=3,5,7。求得了(3,)区间的全部素数。

k=2时,,解得n=7,13,19;,解得n=5,11,17,23。求得了(5,)区间的全部素数。

k=3时

31 7,37 13,43 19
11,41 17,47 23 29

求得了(7,)区间的全部素数。 仿此下去可以一个不漏地求的任何给定数以内的全部素数。由孙子定理知,对于所有可能的值,(1)和(2)式在... 范围内,有

)()()...()....(3)个解.

参考文献(清华大学出版社{品数学}):

二、两个含连续自然数个数相等的区间筛k次被筛数相差不超高k

埃拉特斯特尼筛法是大家熟知的,现在问:两个连续自然数个数相等或者多个自然数相等的区间同时用k个从小到大不同素数筛,被筛掉的数(或者没有被筛掉的数)不同区间会是一样的吗?

将1至...为一组,划分成...个组(或区间)依次按2,3,5,...顺序筛,筛k次后,任两个含连续自然数个 数相等的区间,被筛(或末被筛)数相差不超过k个。

说明:本筛法与埃拉托赛尼筛法不同,埃氏筛先用2筛,然后把2的倍数剔除掉;再用3筛,又把3的倍数剔除掉;再用5筛,.....。本筛法是已经筛过的数不马上剔除掉,而是做上标记,等全部筛完过后再把筛过的数剔除掉。于是,有一些含有几个不同素因子的数就要被筛几遍,例如“6 ”,就要被“2,”和“3,”各筛一遍。

证明:根据除法算式定理:“给定正整数a和b,b不等于0,存在唯一整数a和r,(0≤r<b.)。使a=bq+r。”得知,如果从a中筛bm形数,a个连续自然数中,最多含有q+1个bm形数,r个连续自然数中,最多含有一个bm形数。例如,a=35,b=3,35=3x11+2,35个连续自然数中,最多含有11+1=12个3m形数,例如1---35有11个3m形数,36----70有12个3m形数。

现在设某两个区间为A与B,含自然数的个数分别为|A|与|B|,|A|=|B|,下证明p去筛,两区间被筛pm形数(或者未被筛数)个数相差最多不超过1个。由上所述筛法,用顺序素数依次去筛,两区间每次被筛pm形数(或者未被筛数)个数相差最多不超过1个,故筛k次两区间被筛数(或者未被筛数)个数最多不超过k个。

证法1,设|A|=pm+r,则|B|=pm+r,0≤r<p,即区间A和B中均至少含有m个pm形数,又由于r<p,故r个连续自然数中至多有一个pm形数,即被筛pm形数个数相差不超过1个。

证法2,假若不然,筛k次有两个区间A与B,被筛数相差大于K,比如有K+1个,那会出现什么问题呢?我们问第K+1是个什么(见图),例如A与B用2和3去筛,如果出现了相差3个,第一个记为2m形,第二个记为3m形,问第三个(?)是什么形式?(每一个括号表示一个自然数)。

区间A:(+)。。。(+);------------------------(-)(-)(-)(-)。。。(-);

区间B:(+)。。。(+)(2 m)(3 m)( ? );------------------------(-)。。。(-);

|---------------已经筛过部分----------------------|------------未经筛过部分------------|。

如果第三个(?)是2m或者3m形, 显然与除法算式定理矛盾;如果不是2m或者3m形,它就不应该“站在”已经筛过的行列。无论哪一种情况,假设都不能成立。就是说,几个自然数相等的区间,用k个不同的素数去筛,筛完以后,任何两个区间被筛数(或者剩下的数)相差不会超过k个。证毕。

参考内容如下:http://idea.cas.cn/tosubmit.action

第三部分、证明

如果素数只有有限个,最后一个记为,那么(1)式(2)式就就没有小于p^{2}_{k}平方的解。

【1】将1至...按照为一组,划分成...个组(或区间)

[1,]; [p_{{k-1}}p_{{k}}+1,2]; ....; [...—()+1,...]。

【2】把(1)式(2)式的解数即(3)式()()()...()当做抽屉。

【3】由于假定了(1)式(2)式没有小于p^{2}_{k}的解,第一区间就没有解,因为 < p^{2}_{k}

如果第一区间无解,根据引理:“两个含自然数个数相等的区间筛k次被筛数相差不超k“。其它区间的解数就不会超过k个。
还有.....p_{k-2}-1,个区间,总解数不超过(... p_{k-2}-1)k个。

而:

...p_{k-2}-1) k < (...)k < ()()()...()...(4)

【4】 对比(4)式

第二项(中间项)作为分母,第三项作为分子,一一对应,第三项p_{i}-1对应第二项

 \frac{P_{1}-1}{1}\cdot  \frac{P_{2}-1}{P_{1}}\cdot\frac{P_{3}-1}{P_{2}}\cdot\frac{P_{4}-1}{P_{3}}\cdot\frac{P_{5}-1}{P_{4}}\cdot\frac{P_{6}-1}{P_{5}} \cdots \frac{P_{K-1}-1}{P_{K-2}} \cdot\frac{P_{K}-1}{K} \cdot

除了第一项和第二项分母等于分子外,其他都是每一项分子大于分母。

【5】由于抽屉的数量()()()...()是由孙子定理给出的,而装进抽屉的物品(比如乒乓球).......p_{k-2}-1,) k少于抽屉,至少有一些抽屉是空的,这样就违反了孙子定理,与孙子定理矛盾,必然是错误的。所以,原先假设最后一个素数是,显然是错误的,素数无穷多个。

证毕。