質數定理

質數定理

質數定理是在公元前250年由古希臘數學家埃拉托塞尼提出的篩選素數的方法,即要得到不大於某個自然數N的所有素數,只要在2---N中將不大於√N的素數的倍數全部划去即可,後來又有發展。

素數定理

定理

定理描述素數素數的大致分布情況。 素數的出現規律一直困惑著數學家。一個個地看,素數在正整數中的出現沒有什麼規律。可是總體地看,素數的個數竟然有規可循。對正實數x,定義π(x)為不大於x的素數個數。數學家找到了一些函式來估計π(x)的增長。以下是第一個這樣的估計。 π(x)≈x/ln x 其中ln x為x的自然對數。上式的意思是當x趨近∞,π(x) 和x/ln x的比趨 近1(註:該結果為高斯所發現)。但這不表示它們的數值隨著x增大而接近。 下面是對π(x)更好的估計: π(x)=Li (x) + O (x e^(-(ln x)^(1/2)/15),當 x 趨近∞。 其中 Li(x) = ∫(dt/ln x2,x),而關係式右邊第二項是誤差估計,詳見大O符號。 下表比較了π(x),x/ln x和Li(x): x π(x) π(x) - x/ln(x) Li(x) - π(x) x/π(x)

(如圖所示)

素數定理可以給出第n個素數p(n)的漸近估計: :p(n)~n/ln n. 它也給出從整數中抽到素數的機率。從不大於n的自然數隨機選一個,它是素數的機率大約是1/ln n。 這定理的式子於1798年法國數學家勒讓德提出。1896年法國數學家哈達瑪(Jacques Hadamard)和比利時數學家普森(Charles Jean de la Vallée-Poussin)先後獨立給出證明。證明用到了複分析,尤其是黎曼ζ函式。 因為黎曼ζ函式與π(x)關係密切,關於黎曼ζ函式的黎曼猜想對數論很重要。一旦猜想獲證,便能大大改進素數定理誤差的估計。1901年瑞典數學家Helge von Koch證明出,假設黎曼猜想成立,以上關係式誤差項的估計可改進為 :π(x)=Li (x) + O (x^(1/2) ln x) 至於大O項的常數則還未知道。

初等證明

素數定理有些初等證明只需用數論的方法。第一個初等證明於1949年由匈牙利數學家保羅·艾狄胥(“愛爾多斯”,或“愛爾多希”)和挪威數學家阿特利·西爾伯格合作得出。 在此之前一些數學家不相信能找出不需藉助艱深數學的初等證明。像英國數學家哈代便說過素數定理必須以複分析證明,顯出定理結果的「深度」。他認為只用到實數不足以解決某些問題,必須引進複數來解決。這是憑感覺說出來的,覺得一些方法比別的更高等也更厲害,而素數定理的初等證明動搖了這論調。Selberg-艾狄胥的證明正好表示,看似初等的組合數學,威力也可以很大。 但是,有必要指出的是,雖然該初等證明只用到初等的辦法,其難度甚至要比用到複分析的證明遠為困難。

素數簡介

質數的無窮性的證明

質數的個數是無窮的。最經典的證明歐幾里得證得,在他的《幾何原本》中就有記載。它使用了現在證明常用的方法:反證法。具體的證明如下:
●假設質數只有有限的n個,從小到大依次排列為p1,p2,……,pn,設 N = p1 × p2 × …… × pn,那么,N+1是素數或者不是素數。
●如果N+1為素數,則N+1要大於p1,p2,……,pn,所以它不在那些假設的素數集合中。
●如果N+1為合數,因為任何一個合數都可以分解為幾個素數的積;而N和N+1的最大公約數是1,所以N+1不可能被p1,p2,……,pn整除,所以該合數分解得到的素因數肯定不在假設的素數集合中。
●因此無論該數是素數還是合數,都意味著在假設的有限個素數之外還存在著其他素數。
●對任何有限個素數的集合來說,用上述的方法永遠可以得到有一個素數不在假設的素數集合中的結論。
●所以原先的假設不成立。也就是說,素數有無窮多個。
其他數學家也給出了他們自己的證明。歐拉利用黎曼ζ函式證明了全部素數的倒數之和是發散的,恩斯特·庫默的證明更為簡潔,Hillel Furstenberg則用拓撲學加以了證明。

對於一定範圍內的素數數目的計算

儘管整個素數是無窮的,仍然有人會問“100000以下有多少個素數?”,“一個隨機的100位數多大可能是素數?”。素數定理可以回答此問題。

費馬數2^(2^n)+1

被稱為“17世紀最偉大的法國數學家”的費馬,也研究過質數的性質。他發現,設Fn=2^(2^n)+1,則當n分別等於0、1、2、3、4時,Fn分別給出3、5、17、257、65537,都是質數,由於F5太大(F5=4294967297),他沒有再往下檢測就直接猜測:對於一切自然數,Fn都是質數。這便是費馬數。但是,就是在F5上出了問題!費馬死後67年,25歲的瑞士數學家歐拉證明:
F5=4294967297=641×6700417,它並非質數,而是一個合數
更加有趣的是,以後的Fn值,數學家再也沒有找到哪個Fn值是質數,全部都是合數。目前由於平方開得較大,因而能夠證明的也很少。現在數學家們取得Fn的最大值為:n=1495。這可是個超級天文數字,其位數多達10^10584位,當然它儘管非常之大,但也不是個質數。

梅森質數

17世紀還有位法國數學家叫梅森,他曾經做過一個猜想:2^p-1 ,當p是質數時,2^p-1是質數。他驗算出了:當p=2、3、5、7、17、19時,所得代數式的值都是質數,後來,歐拉證明p=31時,2^p-1是質數。 p=2,3,5,7時,2^p-1都是素數,但p=11時,所得2047=23×89卻不是素數。
還剩下p=67127、257三個梅森數,由於太大,長期沒有人去驗證。梅森去世250年後,美國數學家科勒證明,2^67-1=193707721×761838257287,是一個合數。這是第九個梅森數。20世紀,人們先後證明:第10個梅森數是質數,第11個梅森數是合數。質數排列得這樣雜亂無章,也給人們尋找質數規律造成了困難。
現在,數學家找到的最大的梅森質數是一個有9808357位的數:2^32582657-1。數學家雖然可以找到很大的質數,但質數的規律還是無法循通。

相關猜想

哥德巴赫猜想
哥德巴赫猜想(Goldbach Conjecture)大致可以分為兩個猜想(前者稱“強”或“二重哥德巴赫猜想”後者稱“弱”或“三重哥德巴赫猜想”):1、每個不小於6的偶數都可以表示為兩個奇素數之和;2、每個不小於9的奇數都可以表示為三個奇質數之和。
黎曼猜想
黎曼猜想是一個困擾數學界多年的難題,最早由德國數學家波恩哈德·黎曼提出,迄今為止仍未有人給出一個令人完全信服的合理證明。即如何證明“關於質數方程的所有意義的解都在一條直線”。
此條質數之規律內的質數經過整形,“關於質數的方程的所有意義的解都在一條直線上”化為球體質數分布。
孿生質數猜想
1849年,波林那克提出孿生質數猜想(the conjecture of twin primes),即猜測存在無窮多對孿生
猜想中的“孿生”是指一對質數,它們之間相差2。例如3和5,5和7,11和13,10016957和10016959等等都是孿生質數。
10016957和10016959是發生在第333899位序號質數月的中旬[18±1]的孿生質數。

算術基本定理

任何一個大於1的自然數N,都可以唯一分解成有限個質數的乘積 N=(P_1^a1)*(P_2^a2)......(P_n^an) , 這裡P_1 <... 質數,其諸方冪 ai 是正整數。 
這樣的分解稱為N 的標準分解式。
算術基本定理的內容由兩部分構成:分解的存在性、分解的唯一性(即若不考慮排列的順序,正整數分解為素數乘積的方式是唯一的)。
算術基本定理是 初等數論中一個基本的定理,也是許多其他定理的邏輯支撐點和出發點。
此定理可推廣至更一般的交換代數和代數數論。高斯證明復整數環Z[i]也有唯一分解定理。它也誘導了諸如唯一分解 整環歐幾里得整環等等概念。 更一般的還有 戴德金理想分解定理。

素數等差數列

等差數列數列的一種。在等差數列中,任何相鄰兩項的差相等。該差值稱為 公差。類似7、37、67、97、107、137、167、197。這樣由素數組成的數列叫做等差素數數列。2004年,格林和 陶哲軒證明存在任意長的 素數等差數列。2004年4月18日,兩人宣布:他們證明了“存在任意長度的素數等差數列”,也就是說,對於任意值K,存在K個成等差級數的素數。例如 K=3,有素數序列3, 5, 7 (每兩個差2)……K=10,有素數序列 199, 409, 619, 829, 1039, 1249, 1459, 1669, 1879, 2089 (每兩個差210)。

相關詞條

相關搜尋

熱門詞條

聯絡我們