数学著名定理/欧几里得证明素数的无限性

希腊数学家欧几里得给出了一个优雅的证明，证明存在无限多个素数。它依赖于所有非素数——合数——都可以分解成素数的因子的事实。

欧几里得的证明表明，对于任何有限的素数集合*S*，我们都可以找到一个不属于该集合的素数。(与许多书中所述相反，它不必是某个*n*的前*n*个素数，欧几里得也没有假设它是所有素数的集合。例如，有限集合可以是 { 2, 7, 31 }。)

欧几里得考虑了数字 Π*S*，它是所有有限集合*S*的成员的乘积。(例如，如果*S*是 { 2, 7, 31 }，那么 Π*S*是 2 × 7 × 31 = 434)。然后他在这数字上加了1，得到了 1 + Π*S*。(例如，如果*S*是 { 2, 7, 31 }，那么 1 + Π*S*是 1 + (2 × 7 × 31) = 435)。欧几里得声称这个数字 1 + Π*S* 不能被我们开始使用的有限集合*S*中的任何素数整除。(例如，如果*S*是 { 2, 7, 31 }，那么数字 1 + Π*S*，即 1 + (2 × 7 × 31) = 435，不能被 2, 7 或 31 整除；事实上它是 435 = 3 × 5 × 29)。但 1 + Π*S*，像任何数字一样，要么本身是素数，要么可以被某个不等于自身素数整除。无论哪种方式，我们都有一个不在我们的初始有限集合*S*中的素数。(例如，如果*S*是 { 2, 7, 31 }，那么得到的不在*S*中的新素数是 3, 5 和 29)。

在欧几里得对证明的表述中，他考虑的是*S*中所有素数的最小公倍数，而不是将*S*中所有素数相乘。但不同素数的最小公倍数与其乘积相同。

许多书错误地指出，欧几里得的证明是通过反证法进行的，从只有有限多个素数存在的假设开始。