序?

素數研究是純粹數學的精華，也是支撐現代網絡經濟的基礎。我們在網購時，會發送信用卡賬號等個人信息。為了防止在此過程中個人信息被盜，必須對這些信息進行加密處理。接下來我們會講到，加密處理正是運用了費馬和歐拉等數學家所發現的素數的性質

1?埃拉托斯特尼篩法與素數的發現?

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

????

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

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

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?個素數是?2，那么把?2?圈起來。再按順序排除?2?乘以?2、3、4?的倍數。?

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

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

2素數有無窮個

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

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

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

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

2×3+1=7?

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

2 × 3 × 7 + 1 = 43?

所以43?也是素數。繼續驗算。

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

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

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

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

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

既然素數是“數的原子”，那么如果某些分解方法可以解出不同素數的話，就有點不可思議了。所以絕對不會發生這種事，也就是說，分解質因數只存在唯一一種分解方法，這被稱作“算術基本定理”?？赡軙腥苏J為這看起來是理所當然之事，卻被冠以“基本定理”如此隆重的名號。然而，我們同樣可以想象如果這條定理不成立的話，數學世界又是一番怎樣的景象。感興趣的讀者請參考我個人主頁的補充知識。

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

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

數學家研究素數性質就如同物理學家努力研究物質的基本要素“基本粒子”的性質一樣。分解質因數的方法只有一種，這個定理同時也證明了素數是自然數的最小單位?！八阈g基本定理”的名號也是當之無愧。

3素數的分布存在規律了解素數有無窮個后

如果將素數排成一行

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

能發現存在什么規律呢?從古希臘時期開始，直到現在這個問題依然吸引著數學家的興趣。

發現素數的規律就像是發現元素周期表。19世紀的化學家德米特里·門捷列夫依照原子量排列已發現的原子時，發現其性質中存在周期性規律，并且運用這個規律預言了新的原子的存在。而且，門捷列夫的元素周期表對闡明20?世紀的原子構造發揮了巨大的作用。與此相同，如果能發現數的原子即素數的規律，就能更深入地闡明數的秘密。

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

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

而且，3?位數的素數有143?個，4?位數的素數有1061?個。

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

4?位數的話就是8.5?個數中有一個是素數。

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

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

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

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

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

4用素數判定“帕斯卡三角形”

有關素數的另一個重要問題是開發判斷某個自然數是否是素數的方法。后面我們還會提到，互聯網交易時所使用的密碼需要用到300?位數左右的大素數。發現大量的大素數在保護通信秘密中具有實用意義。

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

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

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

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

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

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

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

右邊的系數與帕斯卡三角形中排列的數字之間的關系也一目了然。

觀察(x + 1)n?展開式的系數，發現n?是素數時，存在特殊的規律。

例如，n = 3、5、7?等素數時，

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

不過，當n?是合數時，部分系數不是n?的倍數。例如在n = 4 =?

2 × 2?中，

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

和(2)進行計算，的展開式應該為

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

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

觀察的系數，?

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

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

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

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

∑編輯?|?Gemini

粉絲福利

送書！

本書闡述了求解微積分的技巧，詳細講解了微積分基礎、極限、連續、微分、導數的應用、積分、無窮級數、泰勒級數與冪級數等內容，旨在教會讀者如何思考問題從而找到解題所需的知識點，著重訓練大家自己解答問題的能力。

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

---

想獲得此書，

文章底部留言，

留言點贊第一名的粉絲（24小時計），

免費獲得此書！

總結

以上是生活随笔為你收集整理的不可思议的素数（上）（文末送书）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。