令人著迷的孤獨質數──《數學大觀念》

• 【科科愛看書】無論何時，只要想到數學就一個頭兩個大？那你肯定還沒看過《數學大觀念：從數字到微積分，全面理解數學的 12 大觀念》！此書從簡單加減到高深微積分，用嶄新的視角連結密碼般的數字和真實人生，循序漸進去探索數學的規律和其中令人讚嘆的美好。讓我們一起將數學砍掉重練，邁向數學偉大的航道吧！

質數？合數？傻傻分不清楚

每一個正整數都能表示若干個 2 的次方之和，而且這個表示法是唯一的。在某種意義上，你可以說 2 的各個次方就像是磚塊，在加法的過程中逐漸砌成正數。在本文中，我們會看到質數也扮演著類似的角色，但這次是利用乘法：每一個正數都可以用唯一的一組質數乘積表示。然而，2 的次方很容易就能找出來，而且沒有什麼數學上的驚喜；反之質數卻棘手得多，而且我們對質數還有很多不了解的地方。

質數是恰好有兩個正因數的正整數，這兩個正因數就是 1 和該數本身。下面列出最初的幾個質數：2、3、5、7、11、13、17、19、23、29、31、37、41、43、47、53、⋯

1 這個數字並不被當作質數，因為它只有一個因數，也就是 1。（其實 1 之所以不被認為是質數還有一個更重要的原因，這點我們很快就會提到。）

請注意，2 是質數中唯一的偶數，有些人可能會因此說它是所有質數中最奇怪的！

擁有三個或更多因數的正整數稱作合數，因為這些數字可由其他更小的因數合成。合數依序有：4、6、8、9、10、12、14、15、16、18、20、21、22、24、25、26、27、28、30、⋯。舉例來說，4 這個數字剛好有三個因數：1、2 和 4。6 則有四個因數：1、2、3 和 6。

請注意，1 也不是合數，數學家將 1 這個數字稱作單位，它是所有整數的因數。

每一個合數都可以表示為若干個質數的乘積。要將 120 分解至只剩下質數，我們可能會寫先下 120=6×20，而 6 和 20 雖然都是合數，但它們都可以被分解成質數，也就是 6=2×3 以及 20=2×2×5。因此，120 = 2 × 2 × 2 × 3 × 5 = 2³3¹5¹

有趣的是，無論我們一開始用什麼方式分解此數，最後得到的質因數分解都是一樣的。這就是唯一分解定理，也稱作算術基本定理，它聲稱每個大於 1 的數字都有一組唯一的質因數分解法。

順帶一提，1 不算是質數的真正原因是：如果我們說他是一個質數，這個定理就無法成立。舉例來說，12 可以分解成2×2×3，但也可以說是 1×1×2×2×3，這樣的話，質因數分解就不會是唯一的了。

愛它，就要知道如何分解它

一旦你知道如何分解一個數字，其實就已經相當了解這個數字了。當我還小的時候，我最喜歡的數字是 9，但隨著我漸漸長大，我喜歡的數字開始變大，甚至更複雜。（比方說，π = 3.14159 …， φ = 1.618 …，e = 2.71828 …，還有，i，這個數字沒有辦法用小數表示）在我開始對無理數進行實驗之前，有一陣子我最喜歡的數字是 2520，因為在那些可以「被一到十都整除」的數目中，這是最小的一個。2520 的質因數分解如下：2520 = 2³3²5¹7¹

一旦你知道某數質因數分解的結果，你就可以立刻確定該數有多少個正因數。舉例來說，2520 的因數一定會是 2a3b5c7d，其中 a 可以是 0、1、2 或 3（四種選擇），b 可以是 0、1 或 2（三種選擇），c 可以是 0 或 1（兩種選擇），d 可以是 0 或 1（兩種選擇）。因此藉由乘法規則，2520 總共有 4×3×2×2=48 個正因數。

算術基本定理的證明利用了下列關於質數的事實（任何一本數論教科書都會在第一章證明這點）：

若 p 是一個質數，且 p 能整除兩個或更多個數字的乘積，那麼在組成這個乘積的各個數字中，p 肯定是其中至少一項的因數。

舉例來說：999,999=333×3003 是 11 的倍數，所以 11 一定能整除 333 或 3003。（事實上，3003=11×273。）這個特性對合數來說就不是每次都能成立了，比方說 60=6×10 是 4 的倍數，但是 4 並無法整除 6 或是 10。

要證明唯一的分解定理，我們先反過來假設有些數字質因數分解的結果不只一組。如果 N 是擁有兩組不同的質因數分解的數字中最小的那一個，表示為：p1p2…pr = N = q1q2…qs

其中所有的 pi 和 qj 項都是質數。因為 N 一定是質數 p1 的倍數，所以 p1 一定是其中一個 qj 項的因數。為了讓標記簡單一些，我們就說 p1 整除 q1 好了。因此，由於 q1 是質數，所以我們一定會得到 q1=p1。所以如果我們將上述等式都除以 p1，就會得到：P2…Pr=N/P1=q2…ps

但現在 N/P1 質因數分解也有兩個不同的結果了，這跟我們之前假設的「N是這種數目中的最小的一個」有所牴觸。

要是在火星，一切將不同

順帶一提，在某些數系中，並非所有數都有唯一的因數分解法。

舉例來說，在火星上，由於所有的火星人都有兩個頭，所以他們在生活中只會用偶數：2、4、6、8、10、12、14、16、18、20、22、24、26、28、30、……

在火星人的數系中，像 6 或 10 這樣的數目會被視為質數，因為在因數分解後，這些數目無法由更小的若干個偶數組成。在這個系統中，質數和合數單純地交替出現，每一個 4 的倍數都是合數（因為 4k=2×2k），而其他的所有偶數（像是 6、10、14、18 等等）都是質數，因為這些數不能被分解成兩個更小的偶數。

讓我們來想想 180 這個數目：6×30 ＝ 180 ＝ 10×18

在火星人的數系中，180 可以被分解成兩種不同的質因數組合，所以在這顆星球的數系中，質因數分解的結果並非獨一無二。

質數會不會消失？

1 到 100 之間恰好有 25 個質數，下一百個數中有 21 個質數，再下一百個數中則有 16 個質數。隨著數字愈來愈大，質數也愈來愈稀有。（但並沒有遵循任何可預測的方式，比如說三百到四百之間有 16 個質數，但四百到五百之間的質數有 17 個。）到了一百萬和一百萬零一百之間的時候，就只有 6 個質數了。質數會愈來愈稀有是很合理的，因為一個大樹底下的數字非常多，所以含有因數的可能性也更高。

我們可以證明一串不含任何質數的 100 個相連數字的確存在，甚至有些完全沒有出現質數的相連數字長達 1000 或 100,0000 個（看你想要多長都可以）。為了說服你接受這個事實，接下來我要立刻給你看 99 個相連的合數（雖然這並非由我首創）。研究一下這 99 個相連的數字：100! + 2, 100! + 3, 100! + 4, . . . , 100! + 100

由於 100!=100×99×98×…×3×2×1，所以這個數一定能被 2 到 100 之間的所有數字整除。接下來想想 100!+53 這樣的數字，由於 53 能整除 100!，所以必定也能整除 100!+53。這個論述可以證明凡是 2 ≤ k ≤ 100，則 100!+k 一定會是 k  的倍數，所以這一定會是合數。

請注意，我們的論述並沒有提到 100!+1 是否為質數，但我們也可以證明這一點。有一個美麗的定理叫做威爾遜定理，它說若且唯若 n 是一個質數，則 (n− 1)!+1 是 n 的倍數。

用幾個較小的數目來實驗看看：1!+1=2 是 2 的倍數；2!+1=3 是 3 的倍數；3!+1=7「不是」4 的倍數；4!+1=25 是 5 的倍數；5!+1=121「不是」6 的倍數；6!+1=721 是 7 的倍數；以此類推。由於 101 是質數，而沃里斯定理表示 100!+1 會是 101 的倍數，所以該數就是合數。因此 100! 到 100!+100 包含了 101 個相連的合數。

因為在極大的數字中質數會變得愈來愈稀少，所以大家自然會好奇是不是在某一數之後就完全不會有質數了。不過就如同歐幾里德在兩千年前告訴我們的，這並不會發生。但可不要就這麼接受他說的話了，好好享受自己證明這點的樂趣吧。

定理：質數有無限多個。

證明：反過來假設質數的數量有上限，那麼一定有一個最大的質數，這裡我們用 P 來表示。現在來看看 P!+1 這個數字，由於 P! 能夠被 2 到 P 之間的所有數字整除，就表示這些數字中沒有一個能整除 P!+1，所以 P!+1 一定有一個大於 P 的質因數，而這跟原本假設的「P是最大的質數」有所牴觸。

雖然我們永遠不會找到最大的質數，但這並沒有阻止數學家和電算科學家繼續尋找更大的質數。在我撰寫這本書的當下，目前已知的最大質數有 17,425,170 位數。光是要寫下這個數字就要花掉比本書多上大約一百倍的紙張，不過，我們也可以只寫成一行：2^57,885,161 − 1

要得知 2ⁿ−1 或 2ⁿ+1 是不是質數，我們有個非常管用的方式，這是為什麼此數可以用如此簡單的方式表達出來。

到底是不是質數？費馬為你驗真身

偉大的數學家費馬曾經證明：如果 p 是奇質數，那麼 2^p−1−1肯定是 p 的倍數。

用最小的幾個奇質數試試看吧：對質數 3、5、7、11 來說，我們能看到 2²−1=3 是 3 的倍數；2⁴−1=15 是 5 的倍數；2⁶−1=63 是 7 的倍數；且 2¹⁰−1=1023 是 11 的倍數。

至於合數，顯然當 n 是偶數的時候，2^n-1−1 一定是奇數，所以此數不可能是 n 的倍數。接著拿最小的幾個奇合數來試試看：9、15、21，我們會看到 2⁸−1=255 不是 9 的倍數；2¹⁴−1=16,383 不是 15 的倍數；2²⁰−1=1,048,575 也不是 21 的倍數（甚至不是 3 的倍數）。

因此根據費馬定理，如果有一個很大的數目 N，使得 2^N-1−1 不是 N 的倍數，那麼我們也可以百分之百確定 N 不是質數，就算不知道 N 的因數為何也無妨！

然而費馬定理的逆論述並不正確，因為的確有某些合數（稱做擬質數）表現得像質數一樣。最小的例子是 341=11×31，具有 2³⁴⁰−1 為 341 的倍數這個特性。雖然已經有人證明擬質數的存在非常稀有，但是仍然有無限多個，好在有方法可以排除它們。

令人著迷的完美數字

質數能運用在許多地方，尤其是電算科學。質數是幾乎所有加密演算法的核心，包括為了能在網路上安全地作金融交易而產生的「公開金鑰密碼系統」。這些演算法多數都是基於一個事實：對我們來說能迅速判斷出某數是否為質數，但截至目前為止，並無法迅速地完成某個大數的因數分解。

舉例來說，如果我隨機相乘兩個 1000 位數的質數並得到一個 2000 位數的答案，任何人或是電腦（除非某天有人打造出了一台量子電腦）能算出原來那兩個質數的機率都微乎其微。基於我們沒有能力分解大數而產生出來的這些密碼（像是 RSA 加密演算法），一般相信是相當安全的。

世人已經為質數著迷了數千年，古希臘人曾說，當一個數字等同於該數所有真因數（除了該數本身以外的各個因數）之和的時候，它就是一個完美的數字（正式名稱為「完全數」）。舉例來說，6 是一個完全數，因為它的真因數 1、2 和 3 的總和是 6。

下一個完全數是 28，它的真因數 1、2、4、7 和 14 總和為 28。再接下去的兩個完全數是 496 和 8128，這有任何規律嗎？讓我們看看這些數字質因數分解的結果：

6 = 2× 3
28 = 4 × 7
496 = 16 × 31
8128 = 64 × 127

你看出其中的規律了嗎？第一個數都是 2 的次方，第二個數都是第一數的兩倍再減 1 的結果，而且是個質數。（這就是為什麼上述等式中沒有 8×15 或是 32×63，因為 15 和 63 都不是質數。）我們可以將這個規律歸納成下面這個定理：

定理：若 2ⁿ−1 是一個質數，則 2ⁿ-1×(2ⁿ−1) 就是一個完全數。

證明：令 p=2ⁿ−1 為質數，而我們的目標是要證明2^n-1p 是完全數。

2ⁿ-1p 的真因數為何？如果排除因數 p，剩下的因數就是簡單的 1、2、4、8、…、2^n-1，其總和就是 2^n-1=p。其他的真因數（不包括2^n-1p）則包括因數 p，所以這些因數之和就是 p(1+2+4+8+…+2n−2)=p(2n−1−1)。因此，真因數的總和會是 p + p(2^n-1−1) = p(1 + (2^n-1−1)) = 2^n-1p 正是待證的結果。

偉大的數學家歐拉（1707 ∼ 1783）證明了所有的完全數都遵循這個形式。在我撰寫這本書的當下，已經被找出的完全數總共有四十八個，而且全部都是偶數。

關於質數，仍有許多神秘未知

有任何完全數是奇數嗎？就目前為止，沒有人知道這個問題的答案。唯一知道的是如果有一個完全數是奇數，那麼這個數目一定超過三百位數，但目前也沒有人能證明它們並不存在。

有許多能夠簡單陳述的未解之謎都跟質數有關係，我們已經說明過目前無法得知是否有無限多個費氏數質數。（已經有人證明出費氏數裡面只有兩個完全平方（1 和 144），也只有兩個完全立方（1 和 8）。）

另外一個未解之謎稱作哥德巴赫猜想，它的猜測是所有大於二的偶數都是兩個質數之和。

同樣地，沒有人能夠證明這個猜想，不過有人證明出如果反例的確存在，那麼這個數字至少會有十九位數。（最近有個類似的問題已經有所突破，2013 年，賀歐夫各特（Harald Helfgott）證明了每一個大於七的奇數都可寫成頂多三個奇質數的和。）

最後，所謂的孿生質數是任意兩個相差 2 的質數。孿生質數的前幾個例子是 3 和 5、5 和 7、11 和 13、17 和 19、29 和 31。

你能看出來為什麼 3、5 和 7 是唯一的「三質數組」嗎？ 雖然已經證實（ 因為古斯塔夫（Gustav Dirichlet）一個定理中的特例）世上有無限多個結尾是 1 的質數（或者結尾是 3、7 或 9），是否有無限多個孿生質數這個問題依然還沒有答案。

不管怎麼樣，正整數就是有趣啦！

讓我們用一個有點可疑的證明來結束這一章，但我希望你好歹還是會同意這個論述。

主張：所有的正整數都很有趣！

證明：你一定會同意前幾個正整數都非常有趣，舉例來說，1 是第一個數字，2 是第一個偶數，3 是第一個奇數，4 既是 2+2 又是 2×2 等等。現在反過來假設並不是所有的數字都很有趣，那就必定會有第一個不有趣的數，我們稱之為 N。但光是這一點就讓 N 變得很有趣！所以不有趣的數字根本不存在。

本文摘自《數學大觀念：從數字到微積分，全面理解數學的 12 大觀念》，貓頭鷹出版。