歐幾里得定理

有時被稱為“歐幾里得第一定理”或歐幾里得原理的定理指出，如果 是一個 素數 且 ，則 或 （其中 表示 整除）。一個 推論 是 (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）指出，雖然 不一定是 素數，但令 為 之後的下一個 素數，數字 據推測始終是一個稱為 幸運素數 的素數，儘管這尚未得到證實。