素數的定義
素數是在中小學課本里面就會出現的數學概念,它指的是隻能夠被 1 和它本身整除的正整數。在正整數中,2, 3, 5, 7, 11 等都是素數。同時,每一個正整數(不小於 2)都可以寫成多個素數的乘積,例如
。從素數的定義可以看出,判斷一個數是否是素數是需要通過“乘法”的。而在數學的研究歷程中,數學家們同樣也關心由素數之間的加法所產生的奇妙結論。
100 以內的素數表
哥德巴赫猜想(Goldbach’s Conjecture)
隨著徐遲的報告文學《哥德巴赫猜想》的問世,哥德巴赫猜想在國內早已家喻戶曉。其中,哥德巴赫猜想包括兩個部分:
- [Theorem] 每一個大於 7 的奇數都可以寫成三個素數之和;
- [Conjecture] 每一個大於 6 的偶數都可以寫成兩個素數之和。
哥德巴赫的手稿
從猜想的陳述來看,如果第 2 部分是正確的,那麼可以根據公式
直接得到第 1 部分是正確的,因此第 2 部分被稱為強哥德巴赫猜想,第 1 部分被稱為弱哥德巴赫猜想。其中哥德巴赫猜想的第 1 部分已經被徹底解決,而哥德巴赫猜想的第 2 部分目前最好的結果被稱為陳氏定理( Chen’s Theorem) 。用數學的語言來說,這兩個定理的陳述分別是:
[Theorem (Vinogradov)]假設
是一個奇數,令
表示關於
的計數函數,其中
都是素數。則存在一個一致有界的函數
(
)對於充分大的奇數
,有以下式子成立
備註:從以上公式可以看出,
換句話說,
弱哥德巴赫猜想成立。
[Theorem (Chen)] 假設
是一個偶數,令
表示關於
的計數函數,其中 是素數, 表示最多為兩個素數的乘積。則當 充分大的時候,有以下式子成立:
其中
備註:
- 在哥德巴赫猜想的研究過程中,通常數學家把偶數可表示為 個素數的乘積與 個素數的乘積之和這個問題,簡稱為 問題。所以,陳景潤證明的 “1+2” 並不是指 1+2 = 3,而指的是對於每一個充分大的偶數,要麼是兩個素數之和,要麼是一個素數加上兩個素數之積。其實可以簡單的理解為 或者 ,在這裡 都是素數。從以上公式可以看出,
- 1920 年,挪威數學家 V.Brun 證明了 “9+9″,開啟了數學家研究哥德巴赫猜想之路;1966 年,中國數學家陳景潤證明了 “1+2″,把素數的篩法推向了頂峰。
孿生素數猜想(Twin Primes Conjecture)
在上千年的素數研究歷程中,除了哥德巴赫猜想,孿生素數(Twin Primes)的研究也是數論中的一個重要課題。所謂孿生素數就是相差為 2 的兩個素數,例如
等等。因此,就有人提出猜想:孿生素數有無窮多對。換句話說,如果用 表示第 個素數,那麼孿生素數猜想就是
. 除了孿生素數本身之外,也有學者猜測,對於所有的正整數
形如
的素數對同樣有無窮多對。於是,在網上就有人對於有限的素數對進行了計算,讓大家更好地看到素數之間的分佈情況。
孿生素數及其推廣
下面是部分關於素數間距(小間距,Small Gaps)的結論:
- 1940 年,Paul Erdos 證明 使得
- 2005 年,Daniel Goldston,Janos Pintz 和 Cem Yildirim 證明
- 2007 年,上述結果被改進為
- 2013 年,張益唐證明了,隨後這個結果被改進到 246。
除了素數之間的小間距之外,素數之間的大間距(Big Gaps)同樣也有很多結論:
- 1931 年,Erik Westzynthius 證明
- 2015 年,Terence Tao 等證明對於某個 和無窮個 成立。
素數定理
在研究素數的過程中,研究素數的分佈規律就是這一切的關鍵所在。其中,素數定理則是描述素數分佈的一個重要結論。類似的,關於孿生素數的分佈也有一個上界的估計。
[素數定理]假設
表示不大於 的所有素數的個數,那麼
[孿生素數個數的上界]假設
表示不大於 的所有孿生素數個數,那麼存在常數
使得
備註:從這兩個定理可以粗糙地刻畫出素數與孿生素數在實數軸的分佈情況,並且可以看出孿生素數相對於素數則是少很多的。因為
素數定理
孿生素數的個數
素數的性質
在中小學的競賽部分,大家總能夠接觸到一個關於素數的定理。
[Theorem (Euclid)]素數有無窮多個。
證明:假設素數是有限個,不妨設為
,那麼
就是合數,但是它卻不能被所有的素數
整除,所以導致矛盾。因此素數是無窮多個。證明完畢。
除此之外,在大學裡面學習級數的時候,通常都會研究 調和級數(Harmonic Series) 的性質。所謂調和級數指的就是所有正整數的倒數和,形如:
從定積分與級數的關係可以得到
並且
也就是說,所有正整數的倒數和是發散的。
利用這種思路,其實可以分析所有素數的倒數和,也就是說
通過歐拉公式可以得到:
兩邊取對數可以得到
由於
,並且
,
可以得到
等式的左邊是發散的,右側的第二項是收斂的,因此右側的第一項(素數的倒數和)是發散的。進一步地,可以得到兩個結論:
- 這裡, 是一個常數。
至此,我們得到了兩個級數的定理:
- [Theorem] 所有正整數的倒數和是發散的;
- [Theorem] 所有素數的倒數和是發散的。
從第 2 個結論同樣可以得到素數是無窮多個。於是,就有數學家猜測如果孿生素數的倒數和是發散的,那麼孿生素數同樣也是無窮多對。但是在 1915 年,數學家 Brun 證明了,孿生素數的倒數和是收斂的,這個收斂的數字也被稱為 Brun 常數。
[Theorem]所有孿生素數的倒數和是收斂的。
證明:通過孿生素數個數的上界公式,可以得到存在
使得對於充分大的 ,有
成立。假設素數序列
使得
都是素數,那麼
,進一步可以得到
對於充分大的 成立。而右側是收斂的,i.e.
因此,孿生素數的倒數和是收斂的。證明完畢。
備註:由於孿生素數的倒數和是收斂的,因此,通過孿生素數的倒數和來證明孿生素數有無窮多對這條路就被封死了。
在研究孿生素數的過程中,其目的是為了研究素數之間的間距究竟能有多小,也就是分析
的上界。同樣的,也可以研究素數之間的間距究竟有多大,並且可以分析其量級大約是多少,此時就需要研究
[Theorem]對於充分大的 而言,在
內,素數之間的最小間隔
同時,素數之間的最大間隔
證明:考慮區間
,通過素數定理可以得到在
區間內的素數大約是
個。於是把該區間
切割成長度為
的子區間,區間的個數為
通過鴿籠原理 (Pigeonhole Principle) 可以得到此定理的結論。
備註:除此之外,證明相鄰素數的間隔沒有上限還可以用構造法。考慮
這 個連續的合數,所以兩個相鄰的素數必在
這個區間兩側。因此相鄰素數的間隔沒有上限,i.e.
Eratosthenes 篩法(Eratosthenes Sieve Method)
Eratosthenes 篩法是數學家 Eratosthenes 提出的一種篩選素數的方法,其思路比較簡單:想要篩選出
中的所有素數,則首先把
中的所有正整數按照從小到大的順序
來排列,然後按照如下步驟執行:
- 讀取數列中當前最小的數 2,然後把 2 的倍數全部刪除;
- 讀取數列中當前最小的數 3,然後把 3 的倍數全部刪除;
- 讀取數列中當前最小的數 5,然後把 5 的倍數全部刪除;(4 已經被第一步去掉了)
- 讀取數列中當前最小的數 7,然後把 7 的倍數全部刪除;(6 已經被第一步去掉了)
- 循環以上步驟直到 中所有的數被讀取或者被刪除。
其算法複雜度為
。
黃色的數為素數
Brun 篩法(Brun Sieve Method)
在數學界發展出各種篩法,其重要目的之一就是為了解決孿生素數猜想和哥德巴赫猜想。除了 Eratosthenes 篩法之外,數學家 V. Brun 也發現了一種篩法,後人稱之為 Brun’s Sieve。其目的就是為了估計孿生素數的上界,進一步得到計算孿生素數的倒數和。其主要結論就是
其中
是一個常數,並且 Brun 通過其篩法可以得到哥德巴赫猜想中的 “9+9″,在哥德巴赫猜想的發展中屬於里程碑式的工作。
Question.研究素數究竟有什麼用?
Answer.為了人類智慧的榮耀。
參考文獻:
- Small and Large Gaps Between Primes, Terence Tao, Latinos in the Mathematical Sciences Conference, 2015.
- Bounded Gaps Beween Primes, Yitang Zhang, 2013.
- Additive Number Theory, Melvyn B.Nathanson, GTM 164.
- http://mathworld.wolfram.com/TwinPrimes.html.
閱讀更多 sandag 的文章