分享本文至 E-mail 信箱
學術引用格式
MLA
APA
EndNote(.enw)

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

  • 【科科愛看書】無論何時,只要想到數學就一個頭兩個大?那你肯定還沒看過《數學大觀念:從數字到微積分,全面理解數學的 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 是質數中唯一的偶數,有些人可能會因此說它是所有質數中最怪的!

2 是質數中唯一的偶數,有些人可能會因此說它是所有質數中最奇怪的!圖/Hiné Mizushima @Flickr

擁有三個或更多因數的正整數稱作合數,因為這些數字可由其他更小的因數合成。合數依序有: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 = 233151

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

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

如果 1 是質數,那麼唯一分解定理就不能成立了。圖/Hiné Mizushima @Flickr

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

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

一旦你知道某數質因數分解的結果,你就可以立刻確定該數有多少個正因數。舉例來說,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 個相連的合數。

連續 101 個相連的合數!圖/Tom Simpson @Flickr

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

定理:質數有無限多個。

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

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

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

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

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

用最小的幾個奇質數試試看吧:對質數 3、5、7、11 來說,我們能看到 22−1=3 是 3 的倍數;24−1=15 是 5 的倍數;26−1=63 是 7 的倍數;且 210−1=1023 是 11 的倍數。

至於合數,顯然當 n 是偶數的時候,2n-1−1 一定是奇數,所以此數不可能是 n 的倍數。接著拿最小的幾個奇合數來試試看:9、15、21,我們會看到 28−1=255 不是 9 的倍數;214−1=16,383 不是 15 的倍數;220−1=1,048,575 也不是 21 的倍數(甚至不是 3 的倍數)。

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

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

令人著迷的完美數字

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

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

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

6 是一個完全數,因為它的真因數 1、2 和 3 的總和是 6!圖/Robin @Flickr

下一個完全數是 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 都不是質數。)我們可以將這個規律歸納成下面這個定理:

定理:若 2n−1 是一個質數,則 2n-1×(2n−1) 就是一個完全數。

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

2n-1p 的真因數為何?如果排除因數 p,剩下的因數就是簡單的 1、2、4、8、…、2n-1,其總和就是 2n-1=p。其他的真因數(不包括2n-1p)則包括因數 p,所以這些因數之和就是 p(1+2+4+8+…+2n−2)=p(2n−1−1)。因此,真因數的總和會是 p + p(2n-1−1) = p(1 + (2n-1−1)) = 2n-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 變得很有趣!所以不有趣的數字根本不存在。

太有趣啦~~~圖/GIPHY


《數學大觀念》書封

 

 

 

 

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

2017 年泛知識節 早腦人必搶的早鳥優惠開跑啦!

「3 大領域 x 150 場分享、體驗、工作坊 x 200 個意見領袖 x 1000 個參與者」2017 年兩岸三地最大知識饗宴 – “泛・知識節" 早鳥票開賣啦!

由泛科知識旗下 PanSci 科學新聞網、 娛樂重擊 Punchline、PanX 泛科技新聞網聯合超強協力夥伴,邀你在兩天內火拼知識,替自己的大腦做個版本升級。11月 11&12 日到泛.知識節直搗知識核心,挑戰與創造未知 ∞ 種可能!手腳迅速,眼光精準的早腦人如你,還不速速搶下早鳥優惠及獨家周邊商品!(購票還贈 TAAZE 讀冊生活折價卷)

>>早鳥優惠只到 10/27<<

關於作者

貓頭鷹是智慧的象徵。1992年創社,以出版工具書為主。經過十多年的耕耘,逐步擴及各大知識領域的開發與深耕。現在貓頭鷹是全台灣最重要的彩色圖解工具書出版社。最富口碑的書系包括「自然珍藏、文學珍藏、台灣珍藏」等圖鑑系列,不但在國內贏得許多圖書獎,市場上也深受讀者喜愛。貓頭鷹的工具書還包括單卷式百科全書,以及「大學辭典」等專業辭典。貓頭鷹還有幾個個性鮮明的小類型,包括《從空中看台灣》等高成本的視覺影像書;純文字類的「貓頭鷹書房」,是得獎連連的知性人文書系;「科幻推進實驗室」則是重新站穩台灣科幻小說市場的新系列,其中艾西莫夫的科幻小說,已經成為台灣讀者的口碑選擇。