數學著名定理/歐幾里得證明素數的無限性

希臘數學家歐幾里得給出了一個優雅的證明，證明存在無限多個素數。它依賴於所有非素數——合數——都可以分解成素數的因子的事實。

歐幾里得的證明表明，對於任何有限的素數集合*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*中所有素數相乘。但不同素數的最小公倍數與其乘積相同。

許多書錯誤地指出，歐幾里得的證明是透過反證法進行的，從只有有限多個素數存在的假設開始。