怎样证明质数是无穷多个的??

cleaner

新来报到,请教前辈们一个小问题~

lcl121

我想要证出1+1等于2就行了

Lightalt

这个是属于GIMPS的范围吧~转……

liqi

定理：质数的个数是无穷的.
【证明】假定质数的个数只有有限多个，设为2，3，...，P
考虑这个数：2*3*...*P+1
是什么数？
由于它不能被2，3，...，P的任一个整除（因为余1），所以只能是：

1.质数，与假设矛盾
2.合数，且有异于2，3，...，P的素因子，设为M，这样我们找到了不同于2，3，...，P的质数，与假设矛盾

总之，质数的个数是无穷的.

碧城仙

呵呵，初三刚学反证法时就做过的题目。

cleaner

谢谢各位~
liqi 说的定理我在其他地方也看到过,我也相信质数是无穷多的,但是还有个问题:
2*3*5*7*11*13+1=30031
30031=59*509
这和上面的定理似乎是矛盾的~

[此贴子已经被作者于2004-6-24 8:27:49编辑过]

liqi

与这一条相符：
2.合数，且有异于2，3，...，P的素因子

lcl121

看不懂，不过是可以证的

liqi

以下是引用wpolly在2004-6-24 14:18:09的发言：

【证明2】易证费马数Fn=2^(2^n)+1两两互质，故诸Fn的质因子构成一无穷质数集合

这是为什么？

hzxswyg

只要证明所有质数的倒数和是一个无穷数，就可以了

abc387987

cleaner说的没有与liqi说的定理矛盾，那个定理可是假设了质数是有限个的。再说你没发现你分解出的30031的另外两个因子也是质数吗？

shaoww

证明：对于任意整数M>0，考虑M+M^2+2，对此偶数，由陈氏定理1+2可得M+M^2+2=p1+p2或者M+M^2+2=p1+p2*p3，其中p1，p2，p3为素数，显然，p1、p2、p3中必有一个大于M。所以素数无穷多。

wreck

n大于2时，n和2n之间至少存在一个质数，所以有无穷多个质数。