欧几里得定理

欧几里得定理是数论中的基本定理，定理指出素数是无限的。该定理有许多著名的证明。

欧几里得的证明[编辑]

欧几里得在他的著作《几何原本》（Book IX, Proposition 20）^[1]提出了以下的证明。

对任何有限素数的集合 ${p_1, p_2, ..., p_n}$ 。令 $P = p_1 ... p_n$ 及 $q = P+1$ 。那么 $q$ 是素数或者不是，二者必居其一：

1. 如果 $q$ 是素数，那么至少有一个素因子 $q$ 不在有限素数集 ${p_1, p_2, ..., p_n}$ 。

2. 如果 $q$ 不是素数，那么存在一个素数因子 $p$ 整除 $q$ ，如果 $p$ 在我们的有限素数集中， $p$ 必然整除 $P$ (既然 $P$ 是素数有限集中所有素数的积)；但是，已知 $p$ 整除 $P+1$ ( $P+1 = q$ )，如果 $p$ 同时整除 $P$ 和 $q$ ， $p$ 必然整除 $P$ 和 $q$ 之差 —— $(P + 1) - P = 1$ 。但是没有素数能整除 $1$ ，即有 $p$ 整除 $q$ 就不存在 $p$ 整除 $P$ 。因此 $p$ 不在有限集 ${p_1, p_2, ..., p_n}$ 中。