证明素数/质数有无限多个

在证明素数有无穷多个之前我们先弄懂一些基本定理：

质数或素数：若大于 1 的整数 p 的所有正因子只有 p 和 1，则称其为质数或素数（prime）； 否则称其为 合数（composite number）。

注意：1既不是素数也不是合数。

算术基本定理：任何一个大于1的自然数 $N$,如果$N$不为质数，那么$N$可以唯一分解成有限个质数的乘积$N=P_1^{a_1}\ast P_2^{a_2}\ast P_3^{a_3}\ast .......\ast P_n^{a_n}$，这里$P_1<P_2<P_3......<P_n$均为质数，其中指数$a_i$是正整数。这样的分解称为$N$ 的标准分解式。例如$24=2^3\ast 3$, 2和3都是素数或质数

下面给出欧几里德在 几何原本 里利用反证法证明素数的无穷性。

1. 首先假设存在一个最大的素数$P$。
2. 然后将从2到$P$之间的所有素数相乘然后再加1：$$N＝2\ast 3\ast 5\ast 7\ast 11\ast .......\ast P+1$$这样就得到了$N$， $N$是一个合数。其中$N>P$。
3. 根据算术基本定理可知，一定存在一个素数$P_i$可以整除$N$， 即$Nmod{P}_i==0$， 由于$(N-1)mod{P}_i=0$， 那么一定有$1mod{P}_i=0$, 由于$P_i$最小为2, 可知不存在这样的$P_i$, 所以N是比P更大的素数，这与假设相矛盾，即证明素数有无穷多个。