题目

如何证明素数又无穷多个?

提问时间：2020-11-18

答案

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