序 

素數(shù)研究是純粹數(shù)學(xué)的精華，也是支撐現(xiàn)代網(wǎng)絡(luò)經(jīng)濟(jì)的基礎(chǔ)。我們在網(wǎng)購時，會發(fā)送信用卡賬號等個人信息。為了防止在此過程中個人信息被盜，必須對這些信息進(jìn)行加密處理。接下來我們會講到，加密處理正是運(yùn)用了費(fèi)馬和歐拉等數(shù)學(xué)家所發(fā)現(xiàn)的素數(shù)的性質(zhì)

1 埃拉托斯特尼篩法與素數(shù)的發(fā)現(xiàn) 

把一個整數(shù)表示分解成其他整數(shù)的乘積，這叫作因數(shù)分解。乘積中的整數(shù)稱為原來整數(shù)的因數(shù)。例如，因為6 = 2 × 3 = 1 × 6，所以 6 的因數(shù)是 1、2、3、6。另外，7 的因數(shù)只有 1 和 7。 

素數(shù)指的是“只有 2 個因數(shù)的整數(shù)?！崩?，7 是素數(shù)，而 6 就不是。 而且，1 的因數(shù)只有 1，即“只有 1 個因數(shù)”，所以不是素數(shù)。實際上， 1 不屬于素數(shù)還有另外一個重要的原因，不過我們到后面再解釋這個原 因 。 此 外 ， 既 不 是 素 數(shù) 也 不 是 1 的 數(shù) 統(tǒng) 稱 為 “ 合 數(shù) ”。 

接下來我們試著從2 到 99 的整數(shù)中找出素數(shù)。首先列出所有的整數(shù): 

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 

第1 個素數(shù)是 2，那么把 2 圈起來。再按順序排除 2 乘以 2、3、4 的倍數(shù)。 

在剩余的數(shù)字中，2 后面出現(xiàn)的是3。沒有排除3 說明3 不是2 的倍數(shù)，所以3 的因數(shù)只有1 和3。從而可以推出，3 是素數(shù)。那么接下來把3 圈起來，再排除3 的倍數(shù)。在剩余的數(shù)字中，3 后面出現(xiàn)的是5，所以5 也是素數(shù)。然后把5 圈起來，再排除5 的倍數(shù)。反復(fù)進(jìn)行以上操作，得出了以下結(jié)果。

最后我們發(fā)現(xiàn)剩下的2、3、5、· · · 都是素數(shù)。這種篩選素數(shù)的方法叫作“埃拉托斯特尼篩法”。因為是按順序篩去合數(shù)。埃拉托斯特尼是公元前3 世紀(jì)活躍在埃及亞歷山大的研究者，他還會出現(xiàn)在第6 章的“測量地球周長”章節(jié)中。直到現(xiàn)在，我們改良了埃拉托尼特尼篩法，并將其運(yùn)用于制作素數(shù)表。

博覽Boolan 點(diǎn)擊領(lǐng)取全球機(jī)器學(xué)習(xí)技術(shù)大會PPT 小程序

2素數(shù)有無窮個

古埃及《萊因德紙草書》中曾記載著素數(shù)。不過，據(jù)說到了古希臘時期，人們明確認(rèn)識到素數(shù)是數(shù)的基本。特別是在公元前300 年左右歐幾里得編寫的《幾何原本》中詳細(xì)研究了素數(shù)的性質(zhì)。

與歐幾里得同時期的德謨克利特提出了“原子論”，認(rèn)為萬物都是由基本單位“ 原子”( a t o m ) 所構(gòu)成。在古希臘語中，“ a t o m ” 的“ t o m ” 是“ 切割、分割” 的意思，“ a ” 是表示否定的接頭詞。也就是說，“ a t o m ” 是“無法分割”的意思。因為整數(shù)可以被因數(shù)分解成素數(shù)，卻不能繼續(xù)分解，所以也可以認(rèn)為素數(shù)是“ 數(shù)的原子” 。有趣的是，“ 原子論” 和“ 素數(shù)”在同一個時期被發(fā)現(xiàn)。雖然無法考證哪一個更早出現(xiàn)，不過也許二者是相互影響、相互發(fā)展。

在歐幾里得《幾何原本》記載的多個素數(shù)性質(zhì)中，最重要的定理是素數(shù)有無窮個。其實，是公元前5 世紀(jì)左右畢達(dá)哥拉斯學(xué)派的人證明了這條定理。

畢達(dá)哥拉斯學(xué)派的人發(fā)明了從已知素數(shù)找出新素數(shù)的方法。例如從2 個素數(shù)2 和3 開始，首先將這兩項相乘后加1，即

2×3+1=7 

7不管是除2還是除3都會余1，所以2和3都不是7的因數(shù)，即7是素數(shù)。證明2、3、7 是素數(shù)后，在將這三項相乘后加1，得到的數(shù)除以上述三項中的任何一個數(shù)都會余1。

2 × 3 × 7 + 1 = 43 

所以43 也是素數(shù)。繼續(xù)驗算。

2 × 3 × 7 × 43 + 1 = 1807這個數(shù)除以2、3、7、43 其中的任何一個數(shù)都會余1。然而，1807 并不是素數(shù)。其實，1807 = 13 × 139 可以用2 個質(zhì)素即13 和39 的乘積表示。1807 用2、3、7、43 其中的任何一個數(shù)都無法整除，因此其分別得到的13 和39 是素數(shù)2、3、7、43 之外新發(fā)現(xiàn)的素數(shù)。那么將最小的13 和上述四個素數(shù)相乘后加1，得到

2 × 3 × 7 × 43 × 13 + 1 = 23479 = 53 × 443 

這樣一來，又出現(xiàn)了53 和443 這兩個新的素數(shù)。將已知素數(shù)相乘后加1，得到的數(shù)都用已知素數(shù)無法乘整除。如果這個數(shù)是素數(shù)的話，就出現(xiàn)了新的素數(shù)。如果是合數(shù)，其因數(shù)中會包含新的素數(shù)。然后把其中較小的素數(shù)與原來的幾個素數(shù)相乘，從而又發(fā)現(xiàn)新的素數(shù)。于是會源源不斷地發(fā)現(xiàn)新的素數(shù)，所以素數(shù)有無窮個。這就是畢達(dá)哥拉斯學(xué)派的人所使用的證明方法。

這個方法雖然可以不斷發(fā)現(xiàn)素數(shù)，但是卻無法證明是否適用于所有素數(shù)。因為素數(shù)的世界存在太多的未解之謎。

用素數(shù)的乘積表示自然數(shù)稱作“分解質(zhì)因數(shù)”。歐幾里得的《幾何原本》中提到了素數(shù)的另一個重要性質(zhì)，即分解質(zhì)因數(shù)只有一種分解方法。例如210 可以分解成2 × 3 × 5 × 7，除此之外沒有其他分解方法。

既然素數(shù)是“數(shù)的原子”，那么如果某些分解方法可以解出不同素數(shù)的話，就有點(diǎn)不可思議了。所以絕對不會發(fā)生這種事，也就是說，分解質(zhì)因數(shù)只存在唯一一種分解方法，這被稱作“算術(shù)基本定理”。可能會有人認(rèn)為這看起來是理所當(dāng)然之事，卻被冠以“基本定理”如此隆重的名號。然而，我們同樣可以想象如果這條定理不成立的話，數(shù)學(xué)世界又是一番怎樣的景象。感興趣的讀者請參考我個人主頁的補(bǔ)充知識。

值得慶幸的是，在我們的自然數(shù)世界里，已經(jīng)證明了“算術(shù)基本定理”，即將自然數(shù)分解成素數(shù)的方法具有唯一性。這也是為什么素數(shù)作為“數(shù)的原子”具有特殊的意義。

在上一節(jié)中，我們曾經(jīng)講過1 不是素數(shù)。如此定義的理由也來自“算術(shù)基本定理”。假設(shè)1 是素數(shù)，那么210 除了分解成2 × 3 × 5 × 7 以外，還可以分解成1 × 2 × 3 × 5 × 7 或者1 × 1 × 1 × 2 × 3 × 5 × 7 等。如果1 是素數(shù)，那么基本定理的定義也變得有些繁瑣，例如“自然數(shù)因數(shù)分解成1 以外的素數(shù)的方法只有1 種”。其實，把1 排除在素數(shù)以外的根本原因在于為了盡可能簡潔明了地表達(dá)這個重要的定理。

數(shù)學(xué)家研究素數(shù)性質(zhì)就如同物理學(xué)家努力研究物質(zhì)的基本要素“基本粒子”的性質(zhì)一樣。分解質(zhì)因數(shù)的方法只有一種，這個定理同時也證明了素數(shù)是自然數(shù)的最小單位。“算術(shù)基本定理”的名號也是當(dāng)之無愧。

3素數(shù)的分布存在規(guī)律了解素數(shù)有無窮個后

如果將素數(shù)排成一行

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,··· 

能發(fā)現(xiàn)存在什么規(guī)律呢?從古希臘時期開始，直到現(xiàn)在這個問題依然吸引著數(shù)學(xué)家的興趣。

發(fā)現(xiàn)素數(shù)的規(guī)律就像是發(fā)現(xiàn)元素周期表。19世紀(jì)的化學(xué)家德米特里·門捷列夫依照原子量排列已發(fā)現(xiàn)的原子時，發(fā)現(xiàn)其性質(zhì)中存在周期性規(guī)律，并且運(yùn)用這個規(guī)律預(yù)言了新的原子的存在。而且，門捷列夫的元素周期表對闡明20 世紀(jì)的原子構(gòu)造發(fā)揮了巨大的作用。與此相同，如果能發(fā)現(xiàn)數(shù)的原子即素數(shù)的規(guī)律，就能更深入地闡明數(shù)的秘密。

在第1 節(jié)中，使用埃拉托斯特尼篩法確定了小于99 的素數(shù)。一位數(shù)的素數(shù)共有4 個，分別是2, 3, 5, 7 兩位數(shù)的素數(shù)共有21, 個，分別是

11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47，53, 59, 61, 67, 71, 73, 79, 83, 89, 97 

而且，3 位數(shù)的素數(shù)有143 個，4 位數(shù)的素數(shù)有1061 個。

1 位數(shù)的自然數(shù)有9 個，所以9/4 ≈ 2.3 個數(shù)中就有一個數(shù)是素數(shù)。2 位數(shù)的話就是4.3 個數(shù)中有一個是素數(shù)。3 位數(shù)的話就是6.3 個數(shù)中有一個是素數(shù)。

4 位數(shù)的話就是8.5 個數(shù)中有一個是素數(shù)。

如上所示，素數(shù)的間隔與位數(shù)成正比。因此，根據(jù)這個數(shù)據(jù)計算比例系數(shù)的話，可以推出如果是N 位數(shù)的數(shù)，那么N × 2.3 個數(shù)中有一個是素數(shù)。

其實，2.3 這個比例系數(shù)就是使用第3 章中出現(xiàn)的自然對數(shù)所表示的ln 10 = 2.302585093 · · · 的近似值。因為對數(shù)有一個性質(zhì)

所以N 位數(shù)的數(shù)量N × ln 10 ≈ N × 2.3 中有一個數(shù)是素數(shù)，那么也可以說中有一個數(shù)是素數(shù)。第3 章中出現(xiàn)的自然常數(shù)e 在此處也發(fā)揮了作用。

數(shù)學(xué)家高斯在15 歲時，就像我們剛才那樣尋找素數(shù)分布的規(guī)律，猜想小于 n 的素數(shù)的個數(shù)為n/ln n 個。高斯的猜想和我們觀察結(jié)果“N 位數(shù)的話，差不多中就有一個數(shù)是素數(shù)”具有相同的意義。隨著位數(shù)的增加，高斯的預(yù)測也越準(zhǔn)確。1896 年，普森和雅克· 阿達(dá)馬分別證明了高斯的預(yù)測，這也是廣為人知的“ 素數(shù)定理”。雖然歐幾里得證明了素數(shù)有無窮個，但是素數(shù)定理更加精確地表示了素數(shù)增加的速度。

除了素數(shù)定理以外，自古以來就存在許多有關(guān)素數(shù)規(guī)律的猜想，其中只有一小部分得到證明。其中最有名的當(dāng)屬孿生素數(shù)有無窮個的猜想。最近有研究在很大程度上推進(jìn)了該猜想的發(fā)展，請參照我個人主頁的補(bǔ)充知識。

4用素數(shù)判定“帕斯卡三角形”

有關(guān)素數(shù)的另一個重要問題是開發(fā)判斷某個自然數(shù)是否是素數(shù)的方法。后面我們還會提到，互聯(lián)網(wǎng)交易時所使用的密碼需要用到300 位數(shù)左右的大素數(shù)。發(fā)現(xiàn)大量的大素數(shù)在保護(hù)通信秘密中具有實用意義。

判斷某個自然數(shù)是否屬于素數(shù)最簡單的方法是依次除以小自然數(shù)，研究是否能夠分解成因數(shù)。例如給定一個數(shù)是4187，依次除以2、3、4··· 如果可以整數(shù)的話就是合數(shù)，即判斷不是素數(shù)。實際上，不需要除到4187，只要到平方根左右即可。例如4187 = 53 × 79，小的因數(shù)53 小于。

但是，如果使用這個方法判定300 位數(shù)是否是素數(shù)，因為的平方根是，所以必須一一驗證是否能夠被個數(shù)整除。所謂的“京速計算機(jī)”可以在1 秒內(nèi)進(jìn)行次的演算。宇宙的年齡有138 億年，差不多 秒，那么，即使用京速計算機(jī)從宇宙誕生起計算到

現(xiàn)在，也只能進(jìn)行 次。這樣還是無法判斷300 位數(shù)是否是素數(shù)。在判斷素數(shù)的方法中，有一個方法使用了帕斯卡三角形。什么是帕斯卡三角形?如下所示: 

帕斯卡三角形從最頂端的1 開始，按照以下規(guī)律排列。(1)各行的兩端都是1。(2)各行的相鄰數(shù)字相加后等于下一行的數(shù)字。

例如我們看一下第2、3、4 行，

很明顯，從第2行向第3行推移時，1 + 1 = 2。從第3行向第4行推移時，1 + 2 = 3。

帕斯卡三角形第(n + 1) 行排列的數(shù)字同時也是(x + 1)n 展開成x 的乘方時所出現(xiàn)的系數(shù)。例如: 

右邊的系數(shù)與帕斯卡三角形中排列的數(shù)字之間的關(guān)系也一目了然。

觀察(x + 1)n 展開式的系數(shù)，發(fā)現(xiàn)n 是素數(shù)時，存在特殊的規(guī)律。

例如，n = 3、5、7 等素數(shù)時，

第一項的1 和最后一項的xn 的系數(shù)都是1，除了這兩項以外，其余的系數(shù)等于n 的倍數(shù)。例如在(x + 1)7 的展開式中出現(xiàn)的系數(shù)7、21、35 都是7的倍數(shù)。

不過，當(dāng)n 是合數(shù)時，部分系數(shù)不是n 的倍數(shù)。例如在n = 4 = 

2 × 2 中，

 的系數(shù)6 就不是n 的倍數(shù)。接下來我們來思考一下關(guān)于一般的n。按照帕斯卡三角形的規(guī)律(1) 

和(2)進(jìn)行計算，的展開式應(yīng)該為

除第一項和最后一項以外，分子中都帶有n。假設(shè)n 是素數(shù)，素數(shù)除了1 和它本身外，不能被其他自然數(shù)整除。因為分母都小于n，所以分母中的數(shù)都無法除以n。因此，系數(shù)n 被保留下來。也就是說，系數(shù)都是n 的倍數(shù)。

然而，如果n 是合數(shù)的話，結(jié)果就不一樣了。例如n = 2 × k，假設(shè)k 是奇數(shù)。將n = 2 × k 代入剛才的展開式，得到

觀察的系數(shù)， 

因為k 是奇數(shù)，所以k(2k ? 1) 也是奇數(shù)。不過又因為n = 2k 是偶數(shù)，所以這個數(shù)無法被n 整除。分子中的n = 2k 剛好被分母中的2 整除。這同樣適用于其他合數(shù)。

也就是說，展開成x的乘方時，除和1以外的系數(shù)如果能被n 整除的話，n 是素數(shù)，否則n 就是合數(shù)。

這看起來是判斷大數(shù)字n 是否是素數(shù)的一個好方法，但是僅靠這個方法還遠(yuǎn)遠(yuǎn)不夠。因為的展開會有(n + 1) 項，如果一一確認(rèn)所有系數(shù)是否為n 的倍數(shù)即分別用2、3、4 · · · 除以n 的話，方法雖然簡單卻十分費(fèi)時。那么有沒有一種高效的方法呢？請聽下次分享…

本文來源《用數(shù)學(xué)的語言看世界》，本書由人民郵電出版社圖靈新知出版。

∑編輯 | Gemini

粉絲福利

送書！

本書闡述了求解微積分的技巧，詳細(xì)講解了微積分基礎(chǔ)、極限、連續(xù)、微分、導(dǎo)數(shù)的應(yīng)用、積分、無窮級數(shù)、泰勒級數(shù)與冪級數(shù)等內(nèi)容，旨在教會讀者如何思考問題從而找到解題所需的知識點(diǎn)，著重訓(xùn)練大家自己解答問題的能力。

本書適用于大學(xué)低年級學(xué)生、高中高年級學(xué)生、想學(xué)習(xí)微積分的數(shù)學(xué)愛好者以及廣大數(shù) 學(xué)教師。本書既可作為教材、習(xí)題集，也可作為學(xué)習(xí)指南，同時還有利于教師備課。

想獲得此書，

文章底部留言，

留言點(diǎn)贊第一名的粉絲（24小時計），

免費(fèi)獲得此書！