素数无穷性的证明

imported

notes

Published

May 21, 2012

素数有无穷多个。现在已知最早的证明方法是欧几里得在他的《几何原本》中提出的，该证明方法如下：

假设只有有限个素数 $p_1,p_2,p_3ldots p_n$ 。令 $N=p_1times p_2times p_3times ldots times p_n$ 。那么，N+1是素数或者不是素数。
如果N+1为素数，则N+1要大于 $p_1,p_2,p_3ldots p_n$ ，所以它不在那些假设的素数集合中。
如果N+1为合数，因为任何一个合数都可以分解为几个素数的积；而N和N+1的最大公约数是1，所以N+1不可能被 $p_1,p_2,p_3ldots p_n$ 整除，所以该合数分解得到的素因数肯定不在假设的素数集合中。
因此无论该数是素数还是合数，都意味着在假设的有限个素数之外还存在着其他素数。
对任何有限个素数的集合来说，用上述的方法永远可以得到有一个素数不在假设的素数集合中的结论。
所以原先的假设不成立。也就是说，素数有无穷多个。

参考资料：