作者 | 大小吴

来源 | 大小吴的数学课堂

素数又称为质数，其定义是在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数；否则称为合数。素数和合数是一组相对的概念（规定1既不是素数也不是合数）。

人类在很早的时候就开始研究素数了，神秘的素数令无数数学家为之魂牵梦绕。在数学中就有一门分支学科专门研究素数（整数）及其性质，称为数论，你一定听闻过我国数学家陈景润攻克哥德巴赫猜想的故事吧，讲的就是这个。

素数从2开始，后续有3、5、7、11等等等等，你是否有这样的疑问：假如素数如果可数，是否可以数完？换句话说，素数是有限个的还是无穷的？

答案是无穷多个的。今天大小吴就将为大家介绍一下“素数有无穷多个”的4种证明方法~

在此之前，我们首先来了解一下“算数基本定理”。

“

算数基本定理:设为一个大于1的自然数，则有

其中为某自然数，是素数，并且在不记素数排列次序的意义下，上式分解是唯一的。

1 Euclid的证明

关于素数有无穷多个的证明，早期经典的证明可以追溯到欧几里得（Euclid）的《几何原本》。这也用到了数学中的反证法。

假设是全部素数，

令,并且为的一个素因数。

则，

否则

所以是一个新的素数，

所以假设不正确，因此素数有无穷多个。

2 Hermite的证明

第二个证明来自法国数学家埃尔米特（Hermite），过程也是非常简洁优美。

考虑任意的正整数，只需证明必存在大于的素数即可。

构造

若为素数，则结论成立；

若为合数，对于任意的正整数，都不能整除，则必存在一个比大的素数，有。

因此素数有无穷多个。

3 利用费马数证明

另一个证明来源于数学史上一个著名的乌龙事件，数学家费马发现对于

前五个数~均为素数，于是他猜想所有的都是素数，费马没给出证明（他经常这样干）。

有趣的是，天降神人数学猛男欧拉发现

利用费马数证明素数无限可以遵循如下思路：

证明费马数两两互素⇒每个费马数都有其独特的素因数（费马素数的素因数即是它本身）⇒无限的费马数对应无限的素数

后面两步比较好理解，现在只需证明的即是费马数两两互素。考虑如下递推式：

对于上述递推关系的证明可以简单地用数学归纳法证明：

1）易知，，则当时，有

成立

2）当时，

也成立

事实上，对于任意两个不同的费马数和，则由递推关系可知

继而由辗转相除法可知

但由于所有的费马数均为奇数，所以

即任意两个费马数互素，证明完毕。

4 数学归纳法

最后一个证明遵循的原理是数学归纳法，非常巧妙。

任取素数，则有，即

因此的素因数中，至少存在1个不等于的素因数，

令，

则的素因数中，存在2个互不相等的素因数、。

同理因为，因此的素因数中，至少存在1个不等于和的素因数，

令，

则的素因数中，存在3个互不相等的素因数、、。

假设至少有个互不相等的素因数，

因为，因此的素因数中，至少存在1个不等于、、

令，

则的素因数中，存在个互不相等的素因数、、、...、。

由数学归纳法可知，素数有无穷多个。

参考文献[1] (德)Martin Aigner，Günter M.Ziegler.数学天书中的证明（第三版）[M].冯荣权等译.高等教育出版社，2009.