目錄

• 前言
• 素數(shù)與其無限性：歐幾里得定理
• 素數(shù)分解的存在性與唯一性：算術(shù)基本定理、歐幾里得引理
• 算術(shù)基本定理的部分應(yīng)用
• 素數(shù)出現(xiàn)規(guī)律的估計：素數(shù)定理
• 素數(shù)的一些有意思的特征
• 未完待續(xù)
  • 各種素性檢驗算法
  • 素數(shù)的用武之地：公鑰密碼學(xué)
  • 尚未被證明的關(guān)于素數(shù)的猜想

前言

初等數(shù)論（elementary number theory）是數(shù)論（也是數(shù)學(xué)）的最古老的分支，它用樸素的方法研究數(shù)的規(guī)律，特別是整數(shù)的相關(guān)性質(zhì)。初等數(shù)論的核心是整除理論和同余理論，而整除理論和同余理論的核心就是本篇的主角——素數(shù)。

素數(shù)與其無限性：歐幾里得定理

素數(shù)（prime number），又稱質(zhì)數(shù)，指大于1的自然數(shù)中，除了1與該數(shù)自身外，無法被其他數(shù)整除的數(shù)，即它只有1和它本身兩個正因數(shù)。

相對地，如果一個大于1的自然數(shù)不是素數(shù)，則稱為合數(shù)（composite number）。

人類對素數(shù)的認識有著非常悠久的歷史。歐幾里得在《幾何原本》（公元前300年左右）中，提出了關(guān)于素數(shù)的第一個基本定理，即數(shù)論中的歐幾里得定理（Euclid's theorem）：

素數(shù)有無限多個。

這不是廢話嗎？（逃

該定理有非常多種證明方法，歐幾里得自己的經(jīng)典證明方法簡述如下。

取一個任意素數(shù)組成的有限集S=(p₁, p₂, ..., p_n)。

令p = p₁ · p₂ · ... · p_n，q = p + 1，那么q是素數(shù)或者合數(shù)。分兩種情況討論：

• q是素數(shù)，但是q?S。
• q是合數(shù)，那么就存在一個質(zhì)因數(shù)ρ整除q。若ρ∈S，則ρ必然整除p。也就是說，ρ同時整除p和q = p + 1，那么ρ應(yīng)該整除q - p = (p + 1) - p = 1。但事實是沒有素數(shù)能整除1，即在ρ整除q的前提下，不存在ρ整除p，因此ρ?S。

綜上所述，對任意有限素數(shù)集S，總有一個素數(shù)不在S中，即存在無限多個素數(shù)。定理得證。

素數(shù)的定義與歐幾里得定理都是如此簡單而優(yōu)雅。下面來看確立了素數(shù)核心地位的重要定理——算術(shù)基本定理。

素數(shù)分解的存在性與唯一性：算術(shù)基本定理、歐幾里得引理

算術(shù)基本定理（fundamental theorem of arithmetic）又稱為正整數(shù)的唯一分解定理（unique factorization theorem），其內(nèi)容為：

對于任何大于1的自然數(shù)：

• 要么本身是素數(shù)。
• 要么可以唯一分解成2個或多個素數(shù)的乘積——即將這些素因數(shù)按大小排列，僅有一種排列方式?；蛘呷绻豢紤]它們的大小次序，就僅有一種分解方式。

用現(xiàn)代的說法陳述之：

N = p₁^α₁ · p₂^α₂ · ... · p_k^α_k［其中p₁ < p₂ < ... < p_k均為素數(shù)，各個指數(shù)α_i > 0］稱為自然數(shù)N > 1的標(biāo)準(zhǔn)分解式。自然數(shù)N的標(biāo)準(zhǔn)分解式是存在且唯一的。

由算術(shù)基本定理可以看出，素數(shù)是一切自然數(shù)的基本元素（怪不得叫“素”數(shù)呢）。也就是說，所有對自然數(shù)的研究，都可以通過唯一分解最終轉(zhuǎn)化為對素數(shù)的研究。

歐幾里得雖然并未給出算術(shù)基本定理的標(biāo)準(zhǔn)化定義（因為在古代沒有冪運算），但他還是在《幾何原本》中給出了證明過程。該證明過程是反證法（proof by contradiction）的經(jīng)典案例，詳述如下。

首先需要證明存在性（existence）。

假設(shè)存在大于1的自然數(shù)不能分解成素數(shù)的乘積，將最小的這個數(shù)記為n，n只可能是素數(shù)或者合數(shù)。

• 若n是素數(shù)，但素數(shù)可以分解成自身的乘積（即p = p），產(chǎn)生矛盾，所以n只能是合數(shù)。
• n是合數(shù)就意味著它可以分解成兩個整數(shù)乘積a · b的形式［注意1 < a, b < n］。按照此前的定義，n是大于1的自然數(shù)中不能分解成素數(shù)乘積的最小的數(shù)，因此a和b都可以分解成素數(shù)的乘積，從而n也可以分解成素數(shù)的乘積，產(chǎn)生矛盾。

綜上所述，標(biāo)準(zhǔn)分解式的存在性得證。

然后需要證明唯一性（uniqueness）。

在證明之前，先引入歐幾里得引理（Euclid's lemma）：

如果一個素數(shù)整除兩個正整數(shù)的乘積，那么這個素數(shù)可以至少整除這兩個正整數(shù)中的一個。即：如果素數(shù)p|ab，那么p|a或p|b成立。

歐幾里得引理可以通過裴蜀定理（Bézout's theorem）證明，此處略去。唯一性的證明思路如下。

假設(shè)存在大于1的自然數(shù)可以用多種方式分解成素數(shù)的乘積，將最小的這個數(shù)記為n，顯然n是個合數(shù)。用兩種方式表示n：
n = p₁ · p₂ · ... · p_k = q₁ · q₂ · ... · q_m［其中各p_i、q_i均為素數(shù)］

根據(jù)歐幾里得引理，p₁|q₁ · q₂ · ... · q_m，所以各q_i中有一個能被p₁整除，不妨設(shè)為q₁。但q₁也是個質(zhì)數(shù)，所以只可能有p₁ = q₁。

所以，比n小的自然數(shù)n' = p₂ · p₃ · ... · p_k也可以分解成n' = q₂ · q₃ · ... · q_m，與n的最小性產(chǎn)生矛盾。標(biāo)準(zhǔn)分解式的唯一性得證。

算術(shù)基本定理將1排除在了素數(shù)之外。因為如果1是素數(shù)，上述唯一性就被破壞了（例如，21可以分解成3 · 7、1 · 3 · 7、1 · 1 · 3 · 7...）。

算術(shù)基本定理的部分應(yīng)用

• 算術(shù)基本定理可以用來證明前文講過的歐幾里得定理，如歐拉、埃爾德什的證明方法。

• 推論：
  如果正整數(shù)N的標(biāo)準(zhǔn)分解式為N = p₁^α₁ · p₂^α₂ · ... · p_k^α_k ，那么N的正因數(shù)個數(shù)為：

σ(N) = ∏_i=1^k (1 + α_i)

而其全體正因數(shù)之和為：

Σ(N) = ∏_i=1^k [ (p_i^α_i+1 - 1) / (p_i - 1) ]

• 利用算術(shù)基本定理還能定義正整數(shù)A、B的最大公約數(shù)（GCD）和最小公倍數(shù)（LCM）。如果A的標(biāo)準(zhǔn)分解式為A = p₁^α₁ · p₂^α₂ · ... · p_k^α_k，B的標(biāo)準(zhǔn)分解式為B = p₁^β₁ · p₂^β₂ · ... · p_k^β_k，那么就有：

gcd(A, B) = p₁^{min(α₁, β₁)} · p₂^{min(α₂, β₂)} · ... · p_k^{min(α_k, β_k)}
lcm(A, B) = p₁^{max(α₁, β₁)} · p₂^{max(α₂, β₂)} · ... · p_k^{max(α_k, β_k)}

素數(shù)個數(shù)規(guī)律的估計：素數(shù)定理

長久以來，素數(shù)的出現(xiàn)規(guī)律一直困擾著數(shù)學(xué)家。單獨地看，素數(shù)在正整數(shù)中的分布似乎無跡可尋。但是從總體看，仍然可以近似估計出一些規(guī)律。

定義素數(shù)計數(shù)函數(shù)（prime counting function）π(x)，它表示小于等于某個實數(shù)x的素數(shù)的個數(shù)。例如，π(10) = 4，因為小于等于10的素數(shù)有2、3、5、7四個。

高斯和勒讓德在18世紀(jì)末分別提出了如下猜想：

lim_x→∞ π(x) / [x / ln x] = 1

該猜想在1896年被阿達馬等人用很復(fù)雜的復(fù)變函數(shù)理論證明，稱為素數(shù)定理（prime number theorum），也叫素數(shù)的漸近分布法則（the asymptotic law of distribution of prime numbers）。

用大白話來講，當(dāng)x很大的時候，π(x)差不多等于x / ln x，即π(x)和x / ln x的相對誤差趨近于0。再換另一種不太嚴(yán)謹?shù)恼f法：從不大于n的正整數(shù)中隨機抽選一個數(shù)，它是素數(shù)的概率大約是1 / ln n。

其中Li(n)是對數(shù)積分。下圖示出素數(shù)定理的兩種表述隨著n值增大的相對誤差變化趨勢，可見第二種估計的相對誤差會更快地收斂到0。

素數(shù)的一些有意思的特征

以下是素數(shù)的其它一些不能被稱為“定理”的有趣特征，有些是顯而易見的，有些則需要思考一下。證明過程就略去了。

• 所有大于10的素數(shù)的個位數(shù)只可能是1、3、7、9。
• 所有大于2的素數(shù)都可以唯一地表示為兩個平方數(shù)之差，即p = a² - b²。
• 若n為大于等于2的正整數(shù)，那么在n到n!之間至少有一個素數(shù)。
• 若n為正整數(shù)，那么在n²到(n + 1)²之間至少有一個素數(shù)。
• 若n為大于等于2的正整數(shù)，那么在2ⁿ - 1和2ⁿ + 1兩個數(shù)中，如果其中一個為素數(shù)，那么另一個必為合數(shù)。
• 存在任意長的一段連續(xù)正整數(shù)，其中的所有數(shù)都是合數(shù)。
• 若素數(shù)p為小于等于n的最大素數(shù)，那么p > n / 2。

未完待續(xù)

本篇主要從理論的角度探索了初等數(shù)論中與素數(shù)相關(guān)的基礎(chǔ)知識。接下來的內(nèi)容會更具實用性，列出大綱如下：

• 如何判斷素數(shù)：各種素性檢驗算法
  • 確定性算法
    • 試除法
    • 埃拉托斯特尼篩法
    • 歐拉篩法（線性篩法）
  • 隨機性算法
    • 費馬小定理與費馬素性檢驗
    • 米勒-拉賓素性檢驗
• 素數(shù)的用武之地：公鑰密碼學(xué)與公鑰加密算法
  • 和女朋友相遇的契機RSA算法
  • 如何選擇安全的大素數(shù)
• 尚未被證明的關(guān)于素數(shù)的猜想

明天早起搬磚，民那晚安晚安。