數(shù)學(xué)實(shí)驗(yàn)之五素?cái)?shù)市公開課獲獎(jiǎng)?wù)n件省名師優(yōu)質(zhì)課賽課一等獎(jiǎng)?wù)n件

數(shù)學(xué)試驗(yàn)之五---素?cái)?shù)中國科學(xué)技術(shù)大學(xué)數(shù)學(xué)系陳發(fā)來1/78試驗(yàn)內(nèi)容素?cái)?shù)個(gè)數(shù)素?cái)?shù)表結(jié)構(gòu)素?cái)?shù)判別最大素?cái)?shù)求解素?cái)?shù)公式素?cái)?shù)分布2/781、素?cái)?shù)個(gè)數(shù)算術(shù)基本定理：任何整數(shù)都能夠分解為設(shè)為全部素?cái)?shù)?？疾?/78假如N為合數(shù)，則N必以一些為因子。這是不可能！即使素?cái)?shù)有沒有窮多個(gè)，但伴隨整數(shù)范圍越來越大，素?cái)?shù)似乎越來越稀少。[1，100]----25[1000,1100]---16[100000,100100]---6[10000000,10000100]---24/782、素?cái)?shù)表結(jié)構(gòu)Eratosthenes篩法23456789101112131415161718192021222324252627282930313233經(jīng)過眾多學(xué)者艱辛努力,D.N.Lehmer于19編織出了10000000以內(nèi)素?cái)?shù)表。5/78試除法假設(shè)我們已經(jīng)找到了前n個(gè)素?cái)?shù)p_1=2,p_2=3,...,p_n,為了尋找下一個(gè)素?cái)?shù)我們從p_n+2開始依次檢驗(yàn)每一個(gè)整數(shù)N,看N是否能被某個(gè)p_i,i=1,2,...,n整除.假如N能被前面某個(gè)素?cái)?shù)整除,則N為合數(shù).不然N即為下一個(gè)素?cái)?shù)p_{n+1}.為提升算法效率，只需用不超出

素?cái)?shù)去除N。6/783、素?cái)?shù)判別威爾遜判別法

n是素?cái)?shù)充要條件是這里

是指a-b被p整除。不過該算法運(yùn)算量為O(nlogn^2),計(jì)算量太大。7/78Fermat判別法假如p是素?cái)?shù)，a與p互素，那么實(shí)際上，大約25前，中國古代數(shù)學(xué)家就發(fā)覺了上述結(jié)論。他們由此得出：如果,則n為素?cái)?shù)。該判別法運(yùn)算量為O(log^3n).8/78

經(jīng)過編程計(jì)算發(fā)覺，反過來結(jié)論并不成立。比如，不過341=11x34為合數(shù)！稱使得成立p為偽素?cái)?shù)。9/78注意同余計(jì)算：深入，偽素?cái)?shù)有多少個(gè)？10/78答案是無窮多個(gè)。實(shí)際上，數(shù)學(xué)家邁羅在19證實(shí)，假如n為偽素?cái)?shù)，那么2^n-1也是偽素?cái)?shù)。不過，同素?cái)?shù)個(gè)數(shù)相比，偽素?cái)?shù)個(gè)數(shù)非常少。比如，在2x10^10之內(nèi)，偽素?cái)?shù)不到素?cái)?shù)百萬分之三。所以，能夠認(rèn)為Fermat定理逆定理幾乎成立。11/78利用偽素?cái)?shù)表，能夠給出判別素?cái)?shù)新方法：假如p不整除2^n-1,則p為合數(shù)；假如p整除2^n-1,且在偽素?cái)?shù)表中，則p為合數(shù)，不然，p是素?cái)?shù)。偽素?cái)?shù)能夠推廣到a-偽素?cái)?shù)。令人驚奇是，存在這么數(shù)p,它對任何a都是偽素?cái)?shù)。比如，561=3x11x17就是這么一個(gè)偽素?cái)?shù)，即12/78這么數(shù)稱為絕對偽素?cái)?shù)，也稱邁克爾數(shù)。假如邁克爾數(shù)只有有限個(gè)，則對n>M,素?cái)?shù)判別變得比較輕易。但邁克爾可能有沒有限個(gè)，這使得直接用Fermat定理判別素性變得困難。13/78n-1檢驗(yàn)法

假設(shè)n-1=FR,F>R,gcd(F,R)=1.假如對F每一個(gè)素因子q都存在一個(gè)整數(shù)a>1滿足則n是素?cái)?shù)。14/78基于廣義黎曼猜測判別1976年，繆內(nèi)發(fā)覺了素性判別與黎曼猜測之間一個(gè)深刻聯(lián)絡(luò)。他結(jié)論是：在廣義黎曼假設(shè)下，存在常數(shù)C,對任何整數(shù)n,若n為合數(shù)，則存在a<C(logn)^2使得15/78維路于1978年指出，上述常數(shù)C=70.由此能夠設(shè)計(jì)以下多項(xiàng)式算法：對任意n,依次對a=1,2,…,70(logn)^2檢驗(yàn)上式是否成立。若對每一個(gè)a都不成立，則n為素?cái)?shù)。不然，n為合數(shù)。上述算法運(yùn)算量為O(logn)^5.16/78１９８０年數(shù)學(xué)家Adleman,Rumely,Cohen和Lenstra研究出一個(gè)非常復(fù)雜、含有高度技巧素?cái)?shù)判別方法，檢驗(yàn)一個(gè)２０位數(shù)素性只需１０秒，對一個(gè)５０位數(shù)，只要１５秒，而一個(gè)１００位數(shù)只用４０秒。假如用試除法，判別一個(gè)５０位數(shù)素性要一百億年！17/78概率判別法Lehmann:給定p,判斷它是否為素?cái)?shù)：（１）選擇一個(gè)小于p隨機(jī)數(shù)a;（２）假如a與p不互素，則p為合數(shù)；（３）計(jì)算J=a^(p-1)modp；（４）假如J<>1或-1,那么p為合數(shù)；（５）假如J=1或-1,那么p不是素?cái)?shù)可能性最多是50%.18/78重復(fù)k次試驗(yàn)，那么p不是素?cái)?shù)可能性不超出1/2^k.利用上述算法能夠產(chǎn)生大隨機(jī)素?cái)?shù)：（1）產(chǎn)生隨機(jī)數(shù)p;（2）確保p不被較小素?cái)?shù)整除。（3）產(chǎn)生隨機(jī)數(shù)a,利用上述算法檢測p素性。直到經(jīng)過屢次測試為止。19/78素性判別多項(xiàng)式算法給定一個(gè)n位整數(shù)，假設(shè)某一算法能在f(n)步內(nèi)判斷出該整數(shù)是否素?cái)?shù)。假如f(n)是一個(gè)多項(xiàng)式話，則稱該算法含有多項(xiàng)式復(fù)雜性，稱該問題是“多項(xiàng)式可解”。假如不存在一個(gè)算法其含有多項(xiàng)式計(jì)算復(fù)雜性，則稱該問題屬于NP問題。20/788月，印度理工大學(xué)計(jì)算機(jī)系三位學(xué)者提出了整數(shù)素性判別多項(xiàng)式算法！即素性判別問題是P類問題。他們指出算法復(fù)雜性普通為O(n^12)。假如提供一些啟發(fā)線索話，算法復(fù)雜性能夠降到O(n^6)甚至O(n^3).一個(gè)令人關(guān)注問題是，該算法是否會(huì)威脅現(xiàn)有RSA公鑰密碼體系安全？21/784、最大素?cái)?shù)Mersenne數(shù)形如數(shù)稱為Mersenne數(shù)。利用Mersenne數(shù)能夠結(jié)構(gòu)出非常大素?cái)?shù)。很顯然，假如n是合數(shù)，則M_n也為合數(shù)，但n為素?cái)?shù)時(shí)，M_n不一定為素?cái)?shù)。比如，M_11=2047=23x89是合數(shù)。22/781644年Mersenne宣稱，對n=2,3,5,13,17,19,31,67,127,257,M_n都是素?cái)?shù)，而且對其它n<257,M_n都是合數(shù)。然而，后人證實(shí)M_67,M_257不是素?cái)?shù)，而M_61,M_89,M_107都是素?cái)?shù)。23/78截止2月,數(shù)學(xué)家僅發(fā)覺了39個(gè)Mersenne素?cái)?shù).

n位數(shù)時(shí)間8614325962198211050333265198313204939751198321609165050198524/78n位數(shù)時(shí)間756839227832199285943325871619941257787378632199613982694209211996297622189593219973021377909526199869725932098960199913466917405394525/78Mersenne數(shù)素性判別方法

定義數(shù)列u_0=4,u_{k+1}=u_k^2-2(modM_n),k=1,2,...,n.假如u_{n-1}=0(modM_n),則M_n為素?cái)?shù).不然,M_n為合數(shù).26/78

關(guān)于Mersenne素?cái)?shù)深入問題：（1）Mersenne素?cái)?shù)是否有沒有窮多個(gè)？（2）對什么樣n,M_n是素?cái)?shù)？是否存在求n公式？最少使M_n為素?cái)?shù)n應(yīng)該含有什么性質(zhì)？（3）假如M_n是合數(shù)，假如分解M_n？27/785、生成素?cái)?shù)公式是否存在單變量整系數(shù)多項(xiàng)式,它只生成素?cái)?shù)而且生成全部素?cái)?shù)?更普通地,是否存在一個(gè)生成素?cái)?shù)多變量函數(shù)公式?假如這么公式不存在,能否找到一個(gè)雖不能給出全部但能給出無窮多個(gè)素?cái)?shù)(且只給出素?cái)?shù))公式?28/78Fermat數(shù)形如F_n=2^{2^n}+1數(shù)被稱為Fermat數(shù)。Fermat宣稱，對全部整數(shù)n,F_n永遠(yuǎn)是素?cái)?shù)。確實(shí),F_0=3,F_1=5,F_2=17,F_3=257,F_4=65537都是素?cái)?shù)。但Euler指出F_5=4294967297=6416700417是合數(shù)。29/78后人驗(yàn)證出F_n(n<=19)均為合數(shù)。所以有些人猜測F_n(n>4)都是合數(shù)。Fermat數(shù)F_n與正多邊形做圖有緊密聯(lián)絡(luò).古代數(shù)學(xué)家認(rèn)為，當(dāng)n為大于6素?cái)?shù)時(shí)，正n邊形不能用圓規(guī)與直尺做出。不過，在1796年，19歲德國數(shù)學(xué)家Gauss找到了用直尺與圓規(guī)做正17邊形方法。這一輝煌結(jié)果轟動(dòng)了整個(gè)數(shù)學(xué)界。30/78五年后他深入證實(shí)了:一個(gè)正n邊行可用直尺與園規(guī)作圖充要條件是,n=2^k或者n=2^kp_1p_2...p_r,其中p_1,p_2,...,p_r為不一樣Fermat數(shù).尤其地,正17邊形能夠用直尺與園規(guī)做出.今后，數(shù)學(xué)家梨西羅與蓋爾美斯給出了正257邊形與正65537邊形做圖法！31/78關(guān)于Fermat數(shù)主要研究問題是：（1）怎樣分解Fermat數(shù)？（2）Fermat素?cái)?shù)是否只有有限個(gè)？（3）Fermat合數(shù)是否有沒有窮多個(gè)？（4）Fermat數(shù)有沒有平方因子？32/78Euler素?cái)?shù)生成公式

Euler曾研究過公式：f(n)=n^2+n+41.能夠驗(yàn)證，當(dāng)n=0,1,…,39時(shí)，f(n)都是素?cái)?shù)，但f(40)是合數(shù)。有趣是，公式能給出相當(dāng)多素?cái)?shù)。33/78公式n^2+n+41有一個(gè)非常奇特性質(zhì).為揭示這一特征,我們考查它二次求根公式判別式d=1^2-4

1

41=-163.163有什么尤其地方？有!請看

34/78作為Hilbert第十問題一個(gè)推論,馬蒂雅舍維奇證實(shí)了:存在一個(gè)多元多項(xiàng)式P(x_1,x_2,...,x_n),其正值組成集合恰好是素?cái)?shù)全體.遺憾是,他并沒有給出怎樣詳細(xì)地結(jié)構(gòu)這么多項(xiàng)式.后經(jīng)眾多數(shù)學(xué)家努力,終于在1977年結(jié)構(gòu)出了一個(gè)含有26個(gè)變量25次素?cái)?shù)生成多項(xiàng)式!

35/786、素?cái)?shù)分布素?cái)?shù)沿?cái)?shù)軸分布

（1）伴隨整數(shù)范圍擴(kuò)大，素?cái)?shù)是不是越來越稀疏？稀疏程度是否單調(diào)地增加？（2）相鄰素?cái)?shù)之間間隔值有哪些?它們各重復(fù)多少次?哪些間隔值重復(fù)次數(shù)多?最大間隔值是多少?隨整數(shù)范圍擴(kuò)大,最大間隔值是否也隨之增大?36/78（3）間隔差為2素?cái)?shù)對是否有沒有窮多個(gè)?更普通地,間隔差為某一個(gè)固定偶數(shù)素?cái)?shù)對是否有沒有窮多個(gè)?是否存在相鄰素?cái)?shù),其間隔值能夠任意大?37/78用

(n)表示不超出n素?cái)?shù)個(gè)數(shù),

(m,n)表示區(qū)間[m,n]內(nèi)素?cái)?shù)個(gè)數(shù).固定d,繪制點(diǎn)列（i,

(3^i,3^i+d)),i=1,2,…,N.38/7839/7840/78將素?cái)?shù)從小到大次序排列p_1=2,p_2=3,...,用d_n=p_{n+1}-p_n表示相鄰素?cái)?shù)間間隔.計(jì)算d_1,d_2,...,d_N(如N=1000,10000),然后將點(diǎn)(p_n,d_n)標(biāo)在平面坐標(biāo)系中.41/7842/7843/7844/7845/78素?cái)?shù)個(gè)數(shù)在二維坐標(biāo)平面上標(biāo)出點(diǎn)列(n,

(n)),n=1,2,...,N(取不一樣N,如1000,10000等).也能夠用折線將點(diǎn)列連接起來.觀察

(n)趨于無窮趨勢.46/7847/7848/7849/7850/78由此猜測關(guān)于素?cái)?shù)個(gè)數(shù)近似公式首先是Gauss于1792年給出,但他當(dāng)初沒能給出證實(shí).勒讓德也曾給出51/78以后，Gauss還給出了近似公式：最靠近公式是由Rieman猜測導(dǎo)出：這里52/781852年，俄國數(shù)學(xué)家切比雪夫證實(shí)了這里a=0.92…,b=1.055.1892年，英國數(shù)學(xué)家希爾維斯特改進(jìn)切比雪夫結(jié)果，得到a=0.956…,b=1.044.1896,Hadamard與Poussin利用復(fù)變函數(shù)理論加以證實(shí).

53/78素?cái)?shù)定理初等證實(shí)于1949年著名數(shù)學(xué)家Erdos取得。Riemann猜測與素?cái)?shù)分布有緊密聯(lián)絡(luò)。不過Riemann猜測至今仍未被證實(shí),它無疑是數(shù)學(xué)上最著名難題之一。54/787、深入思索問題Goldbach猜測

Goldbach于1742年給大數(shù)學(xué)家Euler信中提出了兩個(gè)猜測,即每個(gè)大于6偶數(shù)都能夠表為兩個(gè)奇素?cái)?shù)之和;每個(gè)大于9奇數(shù)能夠表為三個(gè)奇素?cái)?shù)之和.

Euler在隨即復(fù)信中寫道:任何大于6偶數(shù)都是兩個(gè)奇素?cái)?shù)之和,即使我不能證實(shí)它,但我確信無疑這是完全正確定理.這就是著名Goldbach猜測由來.55/78兩百多年來,無數(shù)數(shù)學(xué)家花費(fèi)了大量心血都未能處理這一問題.當(dāng)前，有些人驗(yàn)證到10^14,命題依然正確。19，Hilbert在巴黎世界數(shù)學(xué)家大會(huì)上提出23個(gè)問題供20世紀(jì)數(shù)學(xué)家研究。其中第8問題中將Goldbach猜測作為最主要問題之一提出。56/7819，在第五屆世界數(shù)學(xué)家大會(huì)上，數(shù)學(xué)家蘭道指出，即使證實(shí)下面較弱命題，也是當(dāng)代數(shù)學(xué)所力不能及。任何整數(shù)都能夠表示為不超出C個(gè)素?cái)?shù)之和。19英國數(shù)學(xué)家Hardy在哥本哈根召開數(shù)學(xué)會(huì)議上說，Goldbach猜測困難程度能夠跟任何沒處理數(shù)學(xué)問題想比57/781930年，蘇聯(lián)數(shù)學(xué)家什尼爾列曼證實(shí)，任意整數(shù)都能夠表為不超出k個(gè)素?cái)?shù)之和,且k<800000.1935年，k<=2208（蘇聯(lián)，羅曼諾夫）1936年，k<=71(德國，海爾布倫）1937年，k<=67（意大利，里奇）1950年，k<=20（美國，夏彼得）58/781956年，k<=18（中國，尹文霖）1976年，k<=6(旺格漢）1937，蘇聯(lián)人維諾格拉夫證實(shí)，充分大奇數(shù)能夠表為三個(gè)素?cái)?shù)和。另一條路線：將大偶數(shù)表示為s個(gè)素?cái)?shù)之積加上t個(gè)素?cái)?shù)之和。記為“s+t”.59/78年份證實(shí)者國家結(jié)果1920布龍挪威9+91924拉特馬赫德國7+71938布赫夕太勃蘇聯(lián)5+5;4+41948蘭恩尼匈牙利1+C1956王元中國3+4；3+31962潘乘洞中國1+51962王元中國1+41965布赫夕太勃蘇聯(lián)1+31966陳景潤中國1+260/78Fermat大定理設(shè)n是大于2整數(shù)，則方程

無不存在非平凡整數(shù)解。

61/78Fermat本人證實(shí)了n=4情形。1753年，Euler證實(shí)了n=3.1825年，Dirchlet與Legendre證實(shí)了n=5.1832年，法國女?dāng)?shù)學(xué)家索非熱爾曼證實(shí)：假如n和2n+1為素?cái)?shù)，F(xiàn)ermat大定理成立。1839年，拉梅證實(shí)了n=7.62/781847年，德國數(shù)學(xué)家Kummer證實(shí)了對n<100(除出37,59,67),Fermat定理成立。1983年，德國數(shù)學(xué)家法爾廷斯證實(shí)了：對每個(gè)n>2,方程只有有限個(gè)解。1993年，Princeton大學(xué)教授威爾斯宣告證實(shí)了Fermat定理。但數(shù)學(xué)家發(fā)覺了證實(shí)中一個(gè)漏洞。經(jīng)過九個(gè)月努力63/78威爾斯修正了這一錯(cuò)誤，這標(biāo)志著Fermat大定理被徹底征服。威爾斯證實(shí)完全采取了全新路線，用到了當(dāng)代數(shù)學(xué)許多分支：橢圓曲線論，模形式論，伽羅華表示論等。所謂橢圓曲線是以下形式曲線：64/78橢圓曲線與模形式之間有緊密聯(lián)絡(luò)。50年代，日本數(shù)學(xué)家谷山豐和志村五郎猜測：有理數(shù)域上每條橢圓曲線都存在模形式。被乘為“谷山-志村”猜測。60年代，有些人將Femat方程與橢圓曲線聯(lián)絡(luò)起來。1984年，佛賴證實(shí)，假如Fermat大定理不成，則由Fermat方程確定橢圓曲線不可能是模形式，這與谷山-65/78志村猜測矛盾！所以，要證實(shí)Fermat大定理，只需證實(shí)谷山-志村猜測。威爾斯所做正是證實(shí)了該猜測。66/78大整數(shù)素因子分解正如判斷一個(gè)大數(shù)素性一樣,將一個(gè)大整數(shù)分解為素因子乘積是一件相當(dāng)艱難事情,迄今尚無一個(gè)通用有效方法(試除法顯然是不用考慮).當(dāng)前，最有效素因子分解方法運(yùn)算量大約為O(exp(cL^(1/3)log(L)^(2/3))),其中L為要分解整數(shù)N位數(shù)。

67/78利用現(xiàn)有大型計(jì)算機(jī)能力,能夠分解最大整數(shù)不能超出100位.比如,至今尚無人能分解Fermat數(shù)F_9.讀者能否給出F_6分解?1994年，美國數(shù)學(xué)家PeterShor做出了一項(xiàng)驚人工作。他指出，假如使用量子計(jì)算機(jī)，則因子分解算法運(yùn)算量為

O(L^2log(L)loglog(L)).68/78完全數(shù)

所謂完全數(shù)是指它全部因子(除去它本身)之和等于該完全數(shù).比如,6是一個(gè)完全數(shù).因?yàn)?+2+3=6.下一個(gè)完全數(shù)是28.請讀者找出10000以內(nèi)全部完全數(shù),并對它做素因子分解.你能據(jù)此猜測完全數(shù)通式嗎?完全數(shù)與Mersenne素?cái)?shù)有何聯(lián)絡(luò)?你能由此找到更多完全數(shù)嗎?是否存在奇完全數(shù)?完全數(shù)是否有沒有窮多個(gè)?69/78除6以外,完全數(shù)都有一個(gè)奇妙特征,就是每個(gè)完全數(shù)能夠表為幾個(gè)連續(xù)奇數(shù)之立方和.如28=1^3+2^3.請你對你找出完全數(shù)驗(yàn)證此特征.完全數(shù)另一個(gè)特征是它因子倒數(shù)和為1。如1/2+1/3+1/6=1。把完全數(shù)（除6）各位數(shù)相加得另一數(shù)，這么一直做下去，最終得1。完全數(shù)二進(jìn)制形式為：11…100…070/78孿生素?cái)?shù)