證明不存在最大質數

本週我們將繼續探索數學證明。今天我們將討論一個常見的證明：不存在最大的質數。像往常一樣，我的目標是盡可能用簡單的語言解釋，避免使用複雜的數學符號。不過，在此之前，我先帶給大家每週例行的邏輯謎題。

邏輯謎題

你身處一棟106層樓高的建築物中。樓層編號為0到105（除美國以外，世界大部分地區都採用這種樓層編號方式）。你想測試一下，從哪一層可以安全地將雞蛋丟進地面上一個裝滿羽毛的大盒子裡。你知道從樓頂丟下來的雞蛋會碎，而從0層丟下的雞蛋不會碎。你有兩個雞蛋可以用來做實驗。在最壞的情況下，你最少需要扔多少次才能讓雞蛋落入地面？

答案和解析出現在本欄的最後。

證明不存在最大質數

我將用反證法證明不存在最大質數。換句話說，我將反駁相反的結論──即存在最大質數。

我們把最大的質數稱為_{p_n} ，這表示它是第 n 個質數，讓我們以以下順序標記所有質數：

_p1 = 2， _p2 = 3， _p3 = 5， _p4 = 7，… _pn = ?

考慮如下的數字 N：

N = p ₁ × p ₂ × p ₃ × p ₄ × … × p _n + 1。

如果 N 是質數，那麼沒有比它小的素數能整除它。但是，如果我們用它來整除任何小於等於_{pⁿ 的}質數，則餘數都是 1。這只能用兩種方式解釋：

1. N 本身是質數，它一定大於 p _n 。
2. 存在大於 p _{n 的}質數，能整除 N。

無論如何，我們已經證明存在比 p _n更大的質數。

我們來看一個例子，例如一個較小的質數。假設 31 是最大的質數，我來看看會發生什麼事。在這種情況下：

N = 2×3×5×7×11×13×17×19×23×29×31 + 1 = 1,805,044,411,171

使用質因數計算器，我們發現 1,805,044,411,171 = 1,061,729 × 1,700,099。因此，我們找到了兩個比 31 大的質數：1,061,729 和 1,700,099。

再舉一個例子，假設7是最大的質數。則N = 2×3×5×7 + 1 = 211。對211進行質因數分解檢驗，我們發現211是質數。因此，我們找到了一個比7更大的質數。

無論我們假設哪個質數最大，這種方法都會找到一個較大的質數。

邏輯謎題的答案

14

以下是如何在不超過 14 次跳躍的情況下找到最高安全樓層的方法。

1. 從14樓丟下第一個蛋。如果蛋碎了，則依序測試1樓到13樓。如果蛋碎了，最多要丟14次（第一顆蛋丟1次，第二個蛋丟13次）。否則，返回步驟2。
2. 往上爬13層，從27層丟下第一個蛋。如果蛋碎了，則逐層測試15層到26層。如果蛋碎了，最多需要丟14次（第一顆蛋要丟2次，第二顆蛋最多需要丟12次）。否則，返回步驟3。
3. 往上走12層，從39層丟下第一個蛋。如果蛋碎了，就逐層測試28層到38層。如果蛋碎了，最多要丟14次（第一顆蛋3次，第二顆蛋最多11次）。否則，返回步驟4。
4. 往上攀爬11層，從第50層丟下第一個蛋。如果蛋碎了，則逐層測試第40層到第49層。如果蛋碎了，最多要丟14次（第一顆蛋4次，第二顆蛋最多10次）。否則，返回步驟5。
5. 往上爬10層，從第60層丟下第一個蛋。如果蛋碎了，就逐層測試第51層到第59層。如果蛋殼破裂，最多需要滴落 14 滴（第一個蛋需要 5 滴，第二個蛋最多需要 9 滴）。否則，請轉至步驟 6。
6. 往上走9層，從69層丟下第一個蛋。如果蛋碎了，則逐層測試61層到68層。如果蛋碎了，最多要丟14次（第一顆蛋6次，第二顆蛋最多8次）。否則，轉到步驟7。
7. 向上攀爬8層，從77層丟下第一個蛋。如果蛋碎了，則逐層測試70層到76層。如果蛋碎了，最多要丟14次（第一顆蛋7次，第二顆蛋最多7次）。否則，返回步驟8。
8. 往上爬7層，從第84層丟下第一個蛋。如果蛋碎了，則逐層測試第78層到第83層。如果蛋碎了，最多需要丟14次（第一顆蛋要丟8次，第二顆蛋最多需要丟6次）。否則，進行步驟9。
9. 往上走6層，從90層丟下第一個蛋。如果蛋碎了，就逐層測試85層到89層。如果蛋碎了，最多要丟14次（第一顆蛋9次，第二顆蛋最多5次）。否則，轉到步驟10。
10. 往上走5層，從95層丟下第一個蛋。如果蛋碎了，就逐層測試91層到94層。如果蛋碎了，最多要丟14次（第一顆蛋10次，第二顆蛋最多4次）。否則，轉到步驟11。
11. 往上走4層，從99層丟下第一個蛋。如果蛋碎了，就逐層測試96層到98層。如果蛋碎了，最多需要丟14次（第一顆蛋要丟11次，第二顆蛋最多需要丟3次）。否則，轉到步驟12。
12. 往上走三層，從102層丟下第一個蛋。如果蛋碎了，就依序測試100層和101層。如果蛋碎了，最多需要丟14次（第一顆蛋要丟12次，第二顆蛋最多需要丟2次）。否則，轉到步驟13。
13. 上兩層樓，從104層丟下第一個蛋。如果蛋碎了，就測試103層。如果蛋碎了，最多要丟14次（第一顆蛋13次，第二個蛋1次）。否則，跳到步驟14。
14. 上一層樓，從105樓丟下第一個蛋。如果蛋碎了，最高的安全樓層是104層。如果蛋沒碎，最高的安全樓層是105層。

對於一棟n層建築，一般策略是找到進行第一次墜落的最佳樓層。如果第一次測試通過，則從該樓層向上移動相同層數減1的樓層。如果第二次測試通過，則再次向上移動，但這次的樓層數比上次向上移動的樓層數少1層。如此反复，每次測試之間向上移動的樓層數都比前一次少1層。如果第一次測試失敗，則使用第二個蛋，從該層數範圍內最低的樓層開始，系統地測試最後兩次測試之間的每一層。

注意樓層數的增加順序為 n、n-1、n-2、…1。所有這些增加的總和為 n(n+1)/2。關鍵在於找出 n 的最小整數值，使得級數總和等於或大於建築物的樓層數。

例如，我們來看一棟 500 層樓高的建築（不包括安全的底層），解：

n(n+1)/2 = 500

n(n+1) = 1000

^n² + n - 1000 = 0

6; font-family: 'Open Sans', sans-serif; color: #313131 !important; ">使用勾股定理：

n = (-1 +/- √4001 )/2 ≈ 31.13

然而，樓層數均為整數。因此，我們向上取整至 n=32。所以，對於 500 層樓（如果算上安全的底層，則為 501 層），我們從第 32 層開始進行第一次測試。