素數定理

在數論中，素数定理（英語：Prime number theorem）描述素数在自然數中分佈的漸進情況，給出隨著數字的增大，質數的密度逐漸降低的直覺的形式化描述。1896年法國數學家雅克·阿達馬和比利時數學家德·拉·瓦莱布桑先後獨立給出證明。證明用到了複分析，尤其是黎曼ζ函數。

素数的出現規律一直困惑著數學家。一個個地看，素数在正整數中的出現沒有什麼規律。可是總體地看，素数的個數竟然有規可循。對正實數x，定義π(x)為素数计数函数，亦即不大於x的素数個數。數學家找到了一些函數來估計π(x)的增長。以下是第一個這樣的估計。

\pi (x)\approx {\frac {x}{\ln \,x}}

其中 ln x 為 x 的自然對數。上式的意思是當 x 趨近無限，π(x)與x/ln x的比值趨近 1。但這不表示它們的數值隨著 x 增大而接近。

下面是對π(x)更好的估計：

\pi (x)={\rm {Li}}(x)+O\left(xe^{-{\frac {1}{15}}{\sqrt {\ln \,x}}}\right)

，當x 趨近∞。

其中 ${\rm {Li}}(x)=\int _{2}^{x}{\frac {dt}{\ln \,t}}$ （对数积分），而關係式右邊第二項是誤差估計，詳見大O符號。

敘述

定義 π(x) 為素数计数函数，也就是小於等於x 的質數個數。例如 π(10)=4，因為共有 4 個質數小於等於 10，分別是 2、3、5、7。質數定理的敘述為：當 x 趨近無限，π(x) 和 ${\frac {x}{\ln x}}$ 的比值趨近 1。其數學式寫做

\lim _{x\to \infty }{\frac {\;\pi (x)\;}{\frac {x}{\ln(x)}}}=1

。

淺白的說，當 x 很大的時候，π(x) 差不多等於 ${\frac {x}{\ln x}}$ 。該定理被認為是質數的漸進分布定律，以漸進符號可簡化為

\pi (x)\sim {\frac {x}{\ln x}}

。

注意到，上式並不是說指隨著 x 趨近無限， $\pi (x)$ 與 ${\frac {x}{\ln x}}$ 的差趨近於 0。而是隨著 x 趨近無限， $\pi (x)$ 與 ${\frac {x}{\ln x}}$ 的相對誤差趨近於 0。

因此，質數定理也可以被想像成描述從正整數中抽到素数的概率：從不大於 n 的正整數中隨機選出一個數，它是素数的概率大約是 ${\frac {1}{\ln n}}$ 。

質數定理有一個相關的定理，是關於第 $n$ 個素数 $p_{n}$ 的下界，也就所謂的Rosser定理：

p_{n}>n\ln \,n

關於 $π (x)$ 、 $x / ln x$ 和 $li(x)$ 的數值

下表比較了π(x)，x/ln x和Li(x)：

$x$	${\boldsymbol {\pi }}(x)$ ^[1]	${\boldsymbol {\pi }}(x)-{\frac {x}{\ln x}}$ ^[2]	${\frac {{\boldsymbol {\pi }}(x)}{\frac {x}{\ln x}}}$	${\rm {Li}}(x)-{\boldsymbol {\pi }}(x)$ ^[3]	${\frac {x}{{\boldsymbol {\pi }}(x)}}$
10	4	−0.3	0.921	2.2	2.500
10²	25	3.3	1.151	5.1	4.000
10³	168	23	1.161	10	5.952
10⁴	1,229	143	1.132	17	8.137
10⁵	9,592	906	1.104	38	10.425
10⁶	78,498	6,116	1.084	130	12.740
10⁷	664,579	44,158	1.071	339	15.047
10⁸	5,761,455	332,774	1.061	754	17.357
10⁹	50,847,534	2,592,592	1.054	1,701	19.667
10¹⁰	455,052,511	20,758,029	1.048	3,104	21.975
10¹¹	4,118,054,813	169,923,159	1.043	11,588	24.283
10¹²	37,607,912,018	1,416,705,193	1.039	38,263	26.590
10¹³	346,065,536,839	11,992,858,452	1.034	108,971	28.896
10¹⁴	3,204,941,750,802	102,838,308,636	1.033	314,890	31.202
10¹⁵	29,844,570,422,669	891,604,962,452	1.031	1,052,619	33.507
10¹⁶	279,238,341,033,925	7,804,289,844,393	1.029	3,214,632	35.812
10¹⁷	2,623,557,157,654,233	68,883,734,693,281	1.027	7,956,589	38.116
10¹⁸	24,739,954,287,740,860	612,483,070,893,536	1.025	21,949,555	40.420
10¹⁹	234,057,667,276,344,607	5,481,624,169,369,960	1.024	99,877,775	42.725
10²⁰	2,220,819,602,560,918,840	49,347,193,044,659,701	1.023	222,744,644	45.028
10²¹	21,127,269,486,018,731,928	446,579,871,578,168,707	1.022	597,394,254	47.332
10²²	201,467,286,689,315,906,290	4,060,704,006,019,620,994	1.021	1,932,355,208	49.636
10²³	1,925,320,391,606,803,968,923	37,083,513,766,578,631,309	1.020	7,250,186,216	51.939
10²⁴	18,435,599,767,349,200,867,866	339,996,354,713,708,049,069	1.019	17,146,907,278	54.243
10²⁵	176,846,309,399,143,769,411,680	3,128,516,637,843,038,351,228	1.018	55,160,980,939	56.546
OEIS	A006880	A057835		A057752

歷史

1797年至1798年間，法國數學家勒讓德根據上述的質數表猜測， $\pi (x)$ 大約等於 ${\frac {x}{A\ln x+B}}$ ，其中 $A$ 、 $B$ 是未知的函數。勒讓德於1808年出版一本關於數論的書的第二版，書中他給出更精確的猜測： $A=1$ ， $B=-1.08366$ 。根據高斯自己在1849年的回憶，他在15歲或16歲(1792或1793年)的時候就已經考慮過類似的問題了^[4]。1832年，狄利克雷經過跟高斯的交流之後，給出了一個新的逼近函數 $li(x)$ ，(事實上他是用一個有點不一樣的級數表達式)。勒讓德和狄利克雷的式子皆等價於現在的版本，但如果考慮逼近式與 $\pi (x)$ 的差，而不是比值的話，狄利克雷的式子是準確許多的。

俄國數學家切比雪夫參考了歐拉在1731年的工作，引進了定義在實數軸上黎曼ζ函數，企圖證明質數分布的漸進式，並將他所得到的結果寫成兩篇論文，分別在1848和1850年發表。切比雪夫可以證明，如果 $\lim _{x\to \infty }{\frac {\;\pi (x)\;}{\frac {x}{\ln(x)}}}$ 存在且有限，則它一定是1^[5]。此外，在沒有假設任何結果之下，他也證明當 x 足夠大， ${\frac {\;\pi (x)\;}{\frac {x}{\ln(x)}}}$ 會界在兩個很靠近 1 的數字之間^[6]。雖然切比雪夫的論文沒辦法證明質數定理，但它對 $\pi (x)$ 已經可以推論出伯特蘭-切比雪夫定理：對任何大於 $1$ 的正整數 $n$ ，存在一個質數介於 $n$ 和 $2n$ 之間。

1859年，黎曼提交了一篇關於質數分布的非常重要的報告《論小於給定數值的質數個數（英语：On the Number of Primes Less Than a Given Magnitude）》，這也是黎曼在這個領域的唯一一篇文章。黎曼在報告中使用了創新的想法，將 $\zeta$ 函數的定義解析延拓到整個複數平面，並且將質數的分布與 $\zeta$ 函數的零點緊密的聯繫起來。因此，這篇報告是歷史上首次用複分析的方法研究實函數 $\pi (x)$ 。1896年法國數學家雅克·阿達馬和比利時數學家夏尔-让·德拉瓦莱·普桑先後獨立給出證明。兩個證明延著黎曼的思路繼續拓展，且都使用複分析的工具，其中的關鍵步驟是證明如果複數 $s$ 可以寫成 $1+it$ 的形式，且 $t>0$ ，則 $\zeta (s)\neq 0$ ^[7]。

進入20世紀之後，阿達馬和普桑證明的定理經常被稱作質數定理，定理的其他不同證明也陸陸續續被發現，這之中包括1949年阿特勒·塞爾伯格和艾狄胥·帕爾發現的「初等證明」。原本的證明是既冗長，又複雜，於是有很多後面發現的證明使用了陶伯定理（英语：Tauberian theorem）讓證明變得比較簡短，但卻變得讓人比較難以消化。1980年，美國數學家唐納德·J·紐曼（英语：Donald J. Newman）發現了一個簡潔的證明^[8]^[9]，這可能是目前已知最簡單的證明。不過，證明中使用了柯西積分公式，因此一般不被視為是為初等的證明。

因為黎曼ζ函數與 $\pi (x)$ 關係密切，關於黎曼 $\zeta$ 函數的黎曼猜想對數論很重要。一旦猜想獲證，便能大大改進素数定理誤差的估計。1901年瑞典數學家海里格·馮·科赫證明出，假設黎曼猜想成立，以上關係式誤差項的估計可改進為

\pi (x)={\rm {Li}}(x)+O\left({\sqrt {x}}\ln \,x\right)

至於大O項的常數則還未知道。^{[來源請求]}

初等證明

素数定理有些初等證明只需用數論的方法。第一個初等證明於1949年由匈牙利數學家保羅·艾狄胥和挪威數學家阿特利·西爾伯格合作得出。

在此之前一些數學家不相信能找出不需借助艱深數學的初等證明。像英國數學家哈代便說過素数定理必須以複分析證明，顯出定理結果的「深度」。他認為只用到實數不足以解決某些問題，必須引進複數來解決。

參考資料

^ A006880
^ A057835
^ A057752
^ C. F. Gauss. Werke, Bd 2, 1st ed, 444–447. Göttingen 1863.
^ Costa Pereira, N. A Short Proof of Chebyshev's Theorem. American Mathematical Monthly. August–September 1985, 92 (7): 494–495. JSTOR 2322510. doi:10.2307/2322510.
^ Nair, M. On Chebyshev-Type Inequalities for Primes. American Mathematical Monthly. February 1982, 89 (2): 126–129. JSTOR 2320934. doi:10.2307/2320934.
^ Ingham, A. E. The Distribution of Prime Numbers. Cambridge University Press. 1990: 2–5. ISBN 978-0-521-39789-6.
^ Newman, Donald J. Simple analytic proof of the prime number theorem. American Mathematical Monthly. 1980, 87 (9): 693–696. JSTOR 2321853. MR 0602825. doi:10.2307/2321853.
^ Zagier, Don. Newman's short proof of the prime number theorem. American Mathematical Monthly. 1997, 104 (8): 705–708 [2019-05-03]. JSTOR 2975232. MR 1476753. doi:10.2307/2975232. （原始内容存档于2021-04-20）.

外部链接

[1] A006880

[2] A057835

[3] A057752

[4] C. F. Gauss. Werke, Bd 2, 1st ed, 444–447. Göttingen 1863.

[5] Costa Pereira, N. A Short Proof of Chebyshev's Theorem. American Mathematical Monthly. August–September 1985, 92 (7): 494–495. JSTOR 2322510. doi:10.2307/2322510.

[6] Nair, M. On Chebyshev-Type Inequalities for Primes. American Mathematical Monthly. February 1982, 89 (2): 126–129. JSTOR 2320934. doi:10.2307/2320934.

[7] Ingham, A. E. The Distribution of Prime Numbers. Cambridge University Press. 1990: 2–5. ISBN 978-0-521-39789-6.

[8] Newman, Donald J. Simple analytic proof of the prime number theorem. American Mathematical Monthly. 1980, 87 (9): 693–696. JSTOR 2321853. MR 0602825. doi:10.2307/2321853.

[9] Zagier, Don. Newman's short proof of the prime number theorem. American Mathematical Monthly. 1997, 104 (8): 705–708 [2019-05-03]. JSTOR 2975232. MR 1476753. doi:10.2307/2975232. （原始内容存档于2021-04-20）.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

查论编質數類
公式	卡羅爾（ $（2 n －1） 2 －2$ ）費馬質數（ $2 2 n ＋1$ ）梅森質數（ $2 p －1$ ）雙重梅森質數（ $2 2 p －1 －1$ ）瓦格斯塔夫質數 $（2 p ＋1）／3$ 普羅斯質數（ $k \cdot2 n ＋1$ ）階乘質數（ $n ！\pm1$ ）質數階乘質數（ $p n ＃\pm1$ ）歐幾里得數（ $p n ＃＋1$ ）畢達哥拉斯質數（ $4 n ＋1$ ）皮爾龐特質數（ $2 m \cdot3 n ＋1$ ） Quartan質數（ $x 4 ＋ y 4$ ）（英语：Quartan prime）索利納斯質數（ $2 m \pm2 n \pm1$ ）（英语：Solinas prime）卡倫質數（ $n \cdot2 n ＋1$ ）胡道爾質數（ $n \cdot2 n －1$ ）立方質數（ $x 3 － y 3 ）／（ x － y$ ）萊蘭質數（ $x y ＋ y x$ ）塔別脫質數（ $3\cdot2 n －1$ ）威廉姆斯素数（ $（ b -1）\cdot b n －1$ ）（英语：Williams number）米爾斯質數（［ $A 3 n$ ］） Kynea質數（ $（2 n ＋1） 2 －2$ ）
整數數列	斐波纳契素数盧卡斯質數佩尔質數 NSW質數佩蘭偽質數
屬性	維費里希質數質數對（英语：Wieferich pair）沃尔-孙-孙質數沃爾斯滕霍爾姆質數（英语：Wolstenholme prime）威尔逊素数幸运質數 Fortunate質數（英语：Fortunate number）拉馬努金質數皮萊質數正則質數强質數斯特恩質數超奇異質數（橢圓曲線）（英语：Supersingular prime (algebraic number theory)）超奇異質數（月光理論）好質數超質數希格斯質數高互補歐拉商數唯一質數
基數相關	回文素数反素数循環單位質數 $（10 n －1）／9$ 可交换質數環狀質數可截短質數極小質數精緻質數（英语：Delicate prime）原始質數全循環質數唯一質數快樂質數自我質數 Smarandache–Wellin質數 Strobogrammatic質數（英语：Strobogrammatic prime）二面質數四面質數（英语：Tetradic number）
圖形	孪生質數（ $p ， p ＋2$ ）孪生倍链（ $n \pm 1，2 n \pm 1，4 n \pm 1，\dots$ ）（英语：Bi-twin chain）三胞胎質數（ $p ， p ＋2 或 p ＋4， p ＋6$ ）四胞胎質數（ $p ， p ＋2， p ＋6， p ＋8$ ）質數k元組（英语：Prime k-tuple）表兄弟質數（ $p ， p ＋4$ ）六質數（ $p ， p ＋6$ ）陈質數索菲·熱爾曼／安全質數（ $p ，2 p ＋1$ ）坎寧安鏈（ $p ，2 p \pm 1，4 p \pm 3，8 p \pm 7，...$ ）（英语：Cunningham chain）等差數列（ $p ＋ a\cdotn ， n ＝0，1，2，3，...$ ）（英语：Primes in arithmetic progression）平衡質數（ $連續的 p － n ， p ， p ＋ n$ ）
數量級	超大質數（1,000,000+以上）（英语：Megaprime）已知最大質數列表（英语：List of largest known primes and probable primes）
复数	艾森斯坦質數高斯質數
合数	伪質數卡塔蘭（英语：Catalan pseudoprime）橢圓（英语：Elliptic pseudoprime）欧拉欧拉-雅可比费马弗羅貝尼烏斯（英语：Frobenius pseudoprime）盧卡斯（英语：Lucas pseudoprime）佩蘭索默爾–盧卡斯（英语：Somer–Lucas pseudoprime）強卡邁克爾數殆質數半質數楔形数 Interprime 有害数（英语：Pernicious number）
相關	準質數（英语：Probable prime）產業等級質數非法質數質數公式質數間隙 $X 2 ＋1$ 質數質數定理素数计数函数素性测试
前60個質數	2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281
質數列表

敘述

關於 .mw-parser-output .serif{font-family:Times,serif}π(x)、x / ln x 和 li(x) 的數值

歷史

初等證明

相關條目

參考資料

外部链接

關於 $π (x)$ 、 $x / ln x$ 和 $li(x)$ 的數值