素数个数是无限的证明

素数与公因数
    1、素数 我们知道，大于1，并且除1和它本身外没有其他因数的自然数叫素数(或质数)

    2是最小的素数，除2以外，所有的偶数都不是素数。

    按顺序，下列为一个小素数序列:

    2，3，5，7，11，13，17，19，23，29，31，37，41，43，47，53，59，…

    不是素数的整数a>1称为合数。例如，因为有3|39，所以39是合数。整数1被称为基数，它既不是质数也不是合数。类似地，整数0和所有负整数既不是素数也不是合数。

    关于素数，有如下重要结论：

    ①素数有无穷个。

    证明：假设素数只有有限的n个，从小到大依次排列为p1,p2,...,pn，则 x = (p1·p2·...·pn)+1 显然是不能被p1,p2,...,pn中的任何一个素数整除的，因此x也是一个素数，这和只有n个素数矛盾，所以素数是无限多的。

（更详细的反证法证明请看本文最后单独列出的证明过程）

    这个证明的最早来自亚里士多德，非常漂亮，是反证法的经典应用，这个证明被欧拉称为“直接来自上帝的证明”，历代的数学家也对其评价很高。

    但是，千万不可认为，形如p1·p2·...·pn+1（其中p1,p2,...,pn均为素数）的数就一定是素数！第八届全国青少年信息学奥林匹克联赛（NOIP2002)提高组初赛试题第三题第2小题，写程序运行结果，程序要找的就是形如p1·p2·...·pn+1（其中p1,p2,...,pn均为素数）的数中第一个是合数的整数。

    2*3+1=7 是素数

    2*3*5+1=31 是素数

    2*3*5*7+1=211 是素数

    2*3*5*7*11+1=2311 是素数

    2*3*5*7*11*13+1=30031 不是素数，因为30031=59*509



    虽然最大的素数是不存在的，但是人们却对探知最大的素数乐此不疲。

213466917-1

    这是到目前为止人类所发现的最大素数,它是由Michael在2001年12月7日发现的,这是一个梅森素数,有4,053,946位数字。

    所谓梅森素数,是以17世纪法国修道士M.梅森的名字命名的.梅森在1644年出版的著作《物理数学随感》的序言中宣称,对于n=2,3,5,7,13,17,19,31,67,127,257,数Mn=2n-1是素数,而对于其他所有小于257的数n,Mn是合数.但是,这里出现了5个错误,M67,M257不是素数,而M61,M89,M107是素数.显然,要使Mn是素数,n本身必须是素数,但是反过来,n是素数,Mn却不一定是素数,例如虽然11是素数,可是M11=2047=23X89是合数.

    现在寻找很大的梅森素数时,已经完全依赖于计算机了,可以想象,离开了计算机,我们人类将会落入一种怎样的地步.当D.H.莱默博士这位曾经在梅森素数上花费了许多时光的老学者,亲眼看到了计算机在短短的48秒钟内做完了他20年前花费了700多小时才完成的艰辛劳动,最后证明2257-1是一个合数时,他是多么地感慨万端哪.

    时至今日,人类只找到39个梅森素数.前18个梅森素数是n=2,3,5,7,13,17,19,31,61,89,107,127,521,607,1279,2203,2281,3217时的Mn=2n-1.下表列出了从1961年以来所发现的全部梅森素数.

------------------------------------------------------------------------------

素数是无限的，欧几里得在《几何原本》里面已经给出了证明，现在已经有很多种证明方法了。这里我收集一两个。

证法一：
（一）学过初中的同学都知道n!与n!+1互质。故n!与1、2、3、…..n-1、n互质那么n!+1有2种可能（1）n!+1为素数。(2)n!+1为合数
（1）设a=n!+1为素数 集合A={x|0<x≤n x∈N}有b个素数，则集合B={x|0<x≤n!+1 x∈N}内至少有b+1个素数
（2）设a=n!+1为合数则在集合B\A中至少有2个元素可以被a整除
     易证：c=min{x|x∈B\A 且a/x=h h∈N}为素数。同（1）设集合A内有b个素数。则集合B内至少有b+1个素数
综合（1）、（2）可得：设集合A={x|0<x≤n x∈N}有b个素数，则集合B={x|0<x≤n!+1 x∈N}内至少有b+1个素数。
重复（一）操作可得集合C={x|o<x≤（n!+1）!+1  x∈N}内至少有b+2个素数。
继续沿用（一）的操作，用数学归纳法可证:设集合A={x|0<x≤n x∈N}有b个素数，则集合D={x|o<x≤{[(n!+1)!+1]!+1…..}  (d重括号) 内至少有b+d个素数。
由此：当d→+∞时，e=素数的个数≥b+d=+∞
证明完毕。

证法二：（反证法）
假设素数是有限的，假设素数只有有限的n个，最大的一个素数是p
设q为所有素数之积加上1，那么，q = （ 2 * 3 * 5 * …… * p ）+ 1，显然q比p大，根据假设p是最大的素数，则q不是素数
那么，q可以分解为若干个素数的成绩，也就是q可以被2、3、……、p中的数整除
而q被这2、3、……、p中任意一个整除都会余1，与之矛盾
所以，素数是无限的。
（也可以这样说明：若q能被小于q的数整除，情况有两种，被小于q的素数或被小于q的合数。小于q的素数也就包括在2，3，5，…… p 中，明显不能被他们整除；如果能被小于q的合数m整除，合数m又可以分为两个更小的素数相乘，设m=s*t，则s<m<q，t<m<q，那么q肯定能被s或t中的任何一个整除，而s和t都是小于q的素数，都不能整除q，所以就矛盾。）

上一篇: 中国教育走入冬天
下一篇: 迈出第一步
文章来自: 本站原创
引用通告: 查看所有引用 | 我要引用此文章
Tags: 数学
相关日志: