素数与公因数

　　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