欧几里得定理

有时被称为“欧几里得第一定理”或欧几里得原理的定理指出，如果 是一个 素数 且 ，则 或 （其中 表示 整除）。一个 推论 是 (Conway and Guy 1996)。 算术基本定理 是另一个 推论 (Hardy and Wright 1979)。

欧几里得第二定理指出 素数 的数量是 无限 的。该定理，也称为素数无限性定理，由欧几里得在《几何原本》的命题 IX.20 中证明（Tietze 1965，第 7-9 页）。 Ribenboim (1989) 给出了该定理的九个（和一个半）证明。欧几里得的优雅证明过程如下。给定一个连续 素数 的有限序列 2, 3, 5, ..., ，数字

(1)

当 为第 个 素数 时，被称为第 个 欧几里得数，要么是一个新的 素数，要么是 素数 的乘积。如果 是一个 素数，那么它必须大于之前的 素数，因为 1 加上 素数 的乘积必须大于组成乘积的每个 素数。现在，如果 是 素数 的乘积，那么至少有一个 素数 必须大于 。 可以如下所示。

如果 是 合数 并且没有大于 的素因子，那么它的一个因子（比如 ）必须是序列 2, 3, 5, ..., 中的 素数 之一。 因此它 整除 乘积 。 然而，由于它是 的一个因子，它也 整除 。 但是，一个 整除 两个数 和 的数也 整除 它们的差 ，所以 也必须除以

(2)

然而，为了除以 1， 必须是 1，这与它是序列 2, 3, 5, ... 中的 素数 的假设相矛盾。 因此，如果 是合数，则它至少有一个大于 的因子。 由于 要么是大于 的 素数，要么包含大于 的素因子，因此总能找到一个大于有限序列中最大值的 素数，因此有无限多个 素数。 Hardy (1992) 评论说，这个证明“就像它被发现时一样新鲜和重要”，以至于“两千年没有在它上面留下皱纹”。

类似的论证表明， 必须是 素数 或可被大于 的 素数 整除。 Kummer 使用了此证明的变体，这也是一个反证法。 它假设只存在有限数量的 素数 , , ..., 。 现在定义 并考虑 。 它一定是 素数 的乘积，所以它有一个与 相同的 素数 除数 。 因此， 这是无稽之谈，因此我们通过矛盾证明了最初的假设是错误的。

同样真实的是，存在任意长的 合数 序列。 这可以通过定义来证明

(3)

其中 是一个 阶乘。 那么 个连续数字 , , ..., 是 合数，因为

			(4)
			(5)
			(6)
			(7)
			(8)
			(9)

Guy（1981, 1988）指出，虽然 不一定是 素数，但令 为 之后的下一个 素数，数字 据推测始终是一个称为 幸运素数 的素数，尽管这尚未得到证实。