歐幾里得證明質數有無限多個

大約在西元前 300 年，歐幾里得寫下了一個短到一個段落就寫得完的論證。它從未被改進過，因為它沒辦法再改進。它的主張是質數會一直延續下去，而證明是一個建構：給我任何有限的質數清單，我就能交給你一個不在清單上的質數。

兩千年後，這個論證依然帶有一個好魔術的特質。你清楚地看見每一個步驟。你確切知道它如何收場。而它依然讓人拍案叫絕。

什麼是質數，以及為什麼這個問題重要

質數是大於 1 的整數，它唯一的因數只有 1 和它自己。最前面的幾個是 2、3、5、7、11、13。它們存在於整數之中，就像原子一樣：其他每一個整數，都是把質數乘在一起造出來的。例如，數 30 可以拆成 2 乘以 3 乘以 5，而且基本上只有一種拆法。

既然質數是所有整數的建構單元，自然會問：它們會用完嗎？有沒有最大的質數，超過它之後井就乾了？歐幾里得的答案是沒有，而他所走的路徑優雅到可以一口氣讀完。

設定：假設清單是完整的

這個論證是反證法。你一開始就把反對者想要的一切都讓給他。

現在，在把世上存在的每一個質數都收集進那份清單之後，用它們造出一個新的數。

建構出打破清單的那個數

這是關鍵的一步，值得放慢速度，看看它做了什麼。把清單上所有質數相乘，會得到一個清單上每一個質數都能整除的數。加上 1，同時破壞了所有這些整除性。

當你把 N 除以 p1，你會得到餘數 1，因為乘積（p1 乘以 p2 乘以 ... 乘以 pk）可以被 p1 整除，而加上 1 就把餘數變成 1。同樣的道理適用於 p2、p3，以及清單上的每一個質數。它們沒有一個能整除 N。

矛盾

讓證明站得住腳的反例

許多對歐幾里得證明的通俗說法，就是在這裡走偏的。它們聲稱 N 本身永遠是質數。其實不是，而這個區別很重要。

取清單 {2, 3, 5, 7, 11, 13}。乘積是 2 乘以 3 乘以 5 乘以 7 乘以 11 乘以 13，等於 30030。加 1，你得到 N = 30031。

30031 是質數嗎？不是。

$$30031 = 59 \times 509$$

59 與 509 都是質數，而且都不在清單 {2, 3, 5, 7, 11, 13} 上。這正是證明所預測的：不是 N 是質數，而是 N 的質因數不在清單上。在這個例子中，質因數是 59 與 509，兩個被那份有限清單漏掉的質數。論證得到了驗證，但驗證來自因數，而不是來自 N 本身。

這個證明實際上說了什麼

值得停下來看看這個論證的形狀，因為它異常地乾淨。

你並沒有明確地建構出那個缺少的質數。你也沒有去搜尋它。你證明它必然存在，方法是說明假設它不存在，就會陷入邏輯的死胡同。藏在 N 的因數裡的質數 q，可能很容易找到（如果你試幾個 30031 的小因數，59 與 509 就是如此），也可能大得驚人。證明並不在乎。它的力量來自必然性：不論你交出什麼清單，這個建構都會找到缺口。

這自然地連結到其他以同樣「假設相反，看它崩潰」的精神進行的證明。康托爾的對角論證在更大的尺度上使用同樣的結構：假設存在一份完整的實數清單，然後建構出一個可證明不在其中的實數。歐幾里得的影子清晰可見。

為什麼質數不會完全稀疏到消失

這個證明沒有告訴你的一件事，是質數之間最遠可以相隔多遠，或是任何一個質數之後的下一個質數可能有多大。歐幾里得的論證只保證存在性：在任何有限的集合之外，某處還住著另一個質數。質數在數線上的分布，是一個難得多的問題，直到今天仍是數學中最深的未解領域之一。

這個證明確實告訴你的是結構性的事實。質數無法以任何有限的方式窮盡。你可以奉獻一生來列出質數，而你永遠是在列向一個無限的餘數。你找到的每一個質數都是真的，但你前方的那些也一樣真、一樣多，也一樣是任何有限清單所無法觸及的。

若想感受用乘法和指數建構時，數字能增長得多快，直觀理解指數這篇文章是很自然的搭配：乘積 p1 乘以 p2 乘以 ... 乘以 pk 的增長速度，比你預期的還快，而這個增長正是 N 這麼快就變得這麼大的部分原因。

其中的禪意

歐幾里得的證明已有兩千多年的歷史，此後數學家為同一個結果找到了數以百計的證明。沒有一個讓這一個過時。它保有自己的地位，不是因為它最聰明或最一般，而是因為它最透明。

你一次就看見整個論證。建構是自然的。矛盾是銳利的。沒有任何一步需要你憑信念接受，或相信某部複雜的機器正在做它所宣稱的事。

這個證明要你放在心上的，是一個單一的想法：任何有限的質數清單，本來就是不完整的。不是因為清單選得不好，而是因為質數就是任何有限計數都無法涵蓋的那一類東西。它們屬於無限，就像整數、分數，或是一條線上的點那樣。這個證明並沒有告訴你下一個質數在哪裡。它告訴你，下一個質數永遠都在。

這樣就夠了。這一向就夠了。

至於其他同樣帶有這種必然性精神的結果，古德斯坦定理展示了一個數列，儘管成長到超過任何寫得出來的數，卻總會回到零，用的是同樣的邏輯：「某件事必然發生，因為另一種可能是不可能的。」這一族論證值得認識。每一個都是同一個底層事實的不同角度：數學沒有任何逃生口。結構始終站得住。