在证明素数有无穷多个之前我们先弄懂一些基本定理：
质数或素数：若大于 1 的整数 p 的所有正因子只有 p 和 1，则称其为质数或素数（prime）； 否则称其为 合数（composite number）。
：1既不是素数也不是合数。
算术基本定理：任何一个大于1的自然数 N N N,如果 N N N不为质数，那么 N N N可以唯一分解成有限个质数的乘积 N = P 1 a 1 ∗ P 2 a 2 ∗ P 3 a 3 ∗ . . . . . . . ∗ P n a n N=P_1^{a_1}*P_2^{a_2}*P_3^{a_3}*.......*P_n^{a_n} N=P1a1∗P2a2∗P3a3∗.......∗Pnan，这里 P 1 < P 2 < P 3 . . . . . . < P n P_1<P_2<P_3......<P_n P1<P2<P3......<Pn均为质数，其中指数 a i a_i ai是正整数。这样的分解称为 N N N 的标准分解式。例如 24 = 2 3 ∗ 3 24 = 2^3 * 3 24=23∗3, 2和3都是素数或质数
下面给出欧几里德在 几何原本 里利用反证法证明素数的无穷性。
- 首先假设存在一个最大的素数 P P P。
- 然后将从2到 P P P之间的所有素数相乘然后再加1： N ＝ 2 ∗ 3 ∗ 5 ∗ 7 ∗ 11 ∗ . . . . . . . ∗ P + 1 N＝2 * 3 * 5 * 7 * 11 * ....... * P + 1 N＝2∗3∗5∗7∗11∗.......∗P+1这样就得到了 N N N， N N N是一个合数。其中 N > P N > P N>P。
- 根据算术基本定理可知，一定存在一个素数 P i P_i Pi可以整除 N N N， 即 N m o d P i = = 0 N mod P_i == 0 NmodPi==0， 由于 ( N − 1 ) m o d P i = 0 (N-1) mod P_i = 0 (N−1)modPi=0， 那么一定有 1 m o d P i = 0 1modP_i = 0 1modPi=0, 由于 P i P_i Pi最小为2, 可知不存在这样的 P i P_i Pi, 所以N是比P更大的素数，这与假设相矛盾，即证明素数有无穷多个。