素数个数是无限的证明


素数与公因数
    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

引用内容 引用内容
华东师范大学版的数学9年级教材P94有这样一个命题:
从素数2开始,排在前面的任意多个素数的乘积加1一定也是素数。
这个结论就是错误的。


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

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,所以就矛盾。)

[本日志由 随然 于 2009-01-02 10:56 PM 编辑]
上一篇: 中国教育走入冬天
下一篇: 迈出第一步
文章来自: 本站原创
引用通告: 查看所有引用 | 我要引用此文章
Tags: 数学
相关日志:
评论: 4 | 引用: 155 | 查看次数: 18993
[2010-03-31 11:41 AM | | | 199.76.163.45 | del | 取消审核 | 回复回复]
4#
楼上的,虽然任何两个有理数之间都有无限个无理数,任何两个无理数之间都有无限个有理数。但是无理数总数比有理数总数更多,这个是有定论的,可以通过一一映射来证明。。。
yliang22[2009-01-02 09:48 PM | | | 116.235.48.199 | del | 取消审核 | 回复回复]
地板
证明:假设素数只有有限的n个,从小到大依次排列为p1,p2,...,pn,则 x = (p1·p2·...·pn)+1 显然是不能被p1,p2,...,pn中的任何一个素数整除的,因此x也是一个素数,这和只有n个素数矛盾,所以素数是无限多的。
这个证明是错误的。

  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
这个有冲突。

回复来自 <a href=随然"/> 随然 回复 [2009-01-02 10:14 PM]
不是矛盾的,因为前者说的是不能被p1,p2,...,pn中的任何一个素数整除,后者整除的数是59和509
前者是建立在p1,p2,...,pn就包括了所有素数的基础上,后者的2*3*5*7*11*13没有包括所有素数,因为你知道59和509比他们大,但他们都是素数。
初学高数[2008-11-11 03:16 PM | | | 118.26.234.106 | del | 取消审核 | 回复回复]
板凳
同一级别的无限大。。。相除等于1
马列光[2008-06-25 09:00 AM | | | 125.70.60.24 | del | 取消审核 | 回复回复]
沙发
素数无限大,偶数无限大。那一个更大,能判别吗?望交流!


回复来自 <a href=随然"/> 随然 回复 [2009-01-02 10:22 PM]
我赞同楼上“初等高数”说的:同一级别的无限大。。。相除等于1
这个就像有理数和无理数,任何两个有理数之间都有无限个无理数,任何两个无理数之间都有无限个有理数。你说他们谁更多?
发表评论
昵 称:
密 码: 游客发言不需要密码.
邮 箱: 邮件地址支持Gravatar头像,邮箱地址不会公开.
网 址: 输入网址便于回访.
内 容:
验证码:
选 项:
虽然发表评论不用注册,但是为了保护您的发言权,建议您注册帐号.
字数限制 1 字 | UBB代码 关闭 | [img]标签 关闭