1640年費(fèi)馬在數(shù)論領(lǐng)域留下一個(gè)不可磨滅的足跡，他思考這樣一個(gè)式子：2^(2^n) + 1 的值是否一定為素?cái)?shù)。當(dāng)n取0、1、2、3、4時(shí)，這個(gè)式子對(duì)應(yīng)值分別為3、5、17、257、65 537
，費(fèi)馬發(fā)現(xiàn)這五個(gè)數(shù)都是素?cái)?shù)。
由此，費(fèi)馬提出一個(gè)猜想：形如2^(2^n) + 1的數(shù)一定為素?cái)?shù)。由于F5太大（F5 ＝4 294 967 297），費(fèi)馬沒有再往下繼續(xù)進(jìn)行驗(yàn)證。費(fèi)馬在給朋友的一封信中寫道：“我已經(jīng)發(fā)現(xiàn)形如2^(2^n) + 1的數(shù)永遠(yuǎn)為素?cái)?shù)。很久以前我就向分析學(xué)家們指出了這個(gè)結(jié)論是正確的�！�
費(fèi)馬同時(shí)坦白地承認(rèn)，他自己未能找到一個(gè)完全的證明。
費(fèi)馬所研究的Fn=2^(2^n) + 1這種具有美妙形式的數(shù)，被人稱之為費(fèi)馬數(shù)。就這樣費(fèi)馬提出了一個(gè)猜想：所有費(fèi)馬數(shù)都一定是素?cái)?shù)。費(fèi)馬的判斷是正確的嗎？
要驗(yàn)證費(fèi)馬的猜想并不容易。因?yàn)殡S著n的增大，Fn 迅速增大。比如對(duì)后人來說第一個(gè)需要檢驗(yàn)的F5＝4 294 967 297已經(jīng)是一個(gè)十位數(shù)了。大約過了近百年，他的猜想被證明是錯(cuò)的。費(fèi)馬過分相信自己的直覺，做出了一個(gè)錯(cuò)誤猜測。后來的研究的證明了費(fèi)馬不但是錯(cuò)的，而且是大錯(cuò)特錯(cuò)呢！
1729年12月1日，哥德巴赫在寫給歐拉的一封信中問道：“費(fèi)馬認(rèn)為所有形如2^(2^n) + 1的數(shù)都是素?cái)?shù)，你知道這個(gè)問題嗎？費(fèi)馬說他沒能作出證明。據(jù)我所知，也沒有其他任何人對(duì)這個(gè)問題作出過證明�！�
這個(gè)問題引起了歐拉的興趣。1732年，年僅25歲的歐拉驗(yàn)證發(fā)現(xiàn)了F5 ＝641×6 700 417，其中641=5×27+1，這一結(jié)果意味著F5
是一個(gè)合數(shù)。歐拉之后，又有人發(fā)現(xiàn)F6＝27 477×67 280 421 310 721，也是合數(shù)。令人驚奇的是，陸續(xù)有數(shù)學(xué)家發(fā)現(xiàn)F77，F(xiàn)8……，直到F19以及許多n值很大的Fn全都是合數(shù)。
此后人們對(duì)更多的費(fèi)馬數(shù)進(jìn)行了驗(yàn)證。計(jì)算機(jī)的發(fā)明使計(jì)算的過程大大簡化了，計(jì)算機(jī)成為數(shù)學(xué)家研究費(fèi)馬數(shù)的有力工具。但即使如此，在所知的費(fèi)馬數(shù)中竟然沒有再添加一個(gè)費(fèi)馬素?cái)?shù)。迄今為止，費(fèi)馬素?cái)?shù)除了被費(fèi)馬本人所證實(shí)的那五個(gè)外竟然沒有再發(fā)現(xiàn)一個(gè)！因此人們開始猜想：在所有的費(fèi)馬數(shù)中，除了前五個(gè)是素?cái)?shù)外，其他的都是合數(shù)。但是目前能判斷它是素?cái)?shù)還是合數(shù)的也只有幾十個(gè)，除費(fèi)爾馬當(dāng)年給出的5個(gè)外，至今尚未有新的素?cái)?shù)發(fā)現(xiàn)。人們開始猜測：費(fèi)馬數(shù)是否只有有限個(gè)？除了那5個(gè)素?cái)?shù)之外，是否再也沒有了？這兩個(gè)問題至今也沒有解決，成為數(shù)學(xué)中的一個(gè)謎。
費(fèi)馬數(shù)與尺規(guī)作圖：出人意料的結(jié)合
二千多年前，古希臘數(shù)學(xué)家曾深入研究過一類作圖問題，即：如何利用尺規(guī)作內(nèi)接正多邊形。早在《幾何原本》一書中，歐幾里得就用尺規(guī)完成了圓內(nèi)接正三邊形、正四邊形、正五邊形，甚至正十五邊形的作圖問題。然而，似乎更容易完成的正7、9、11……邊形卻未能做出。讓后來數(shù)學(xué)家尷尬的是，歐幾里得之后的2000多年中，有關(guān)正多邊形作圖仍停留在歐幾里得的水平上，未能向前邁進(jìn)一步。
因此，我們可以想象得到，當(dāng)1796年年僅19歲的高斯宣布他發(fā)現(xiàn)了正十七邊形的作圖方法時(shí)，會(huì)在數(shù)學(xué)界引起多么巨大的震憾了。
不過，高斯的結(jié)果多少顯得有些奇怪。他沒有完成正七邊形或正九邊形等的作圖，卻偏偏隔下中間這一些直接完成了正十七邊形。為什么第一個(gè)新做出的正多邊形是正十七邊形而不是正七、九邊形呢？
在高斯的偉大發(fā)現(xiàn)之后，問題仍然存在：正七邊形或正九邊形等是否可尺規(guī)完成？或者更清楚地闡述這個(gè)問題：正多邊形的邊數(shù)具有什么特征時(shí)，它才能用尺規(guī)做出？
在經(jīng)過繼續(xù)研究后，高斯最終在1801年對(duì)整個(gè)問題給出了一個(gè)漂亮的回答。高斯指出，如果僅用圓規(guī)和直尺，作圓內(nèi)接正n邊形，當(dāng)n滿足如下特征之一方可做出：
（1）n=2m；（ 為正整數(shù)） （2）邊數(shù)n為素?cái)?shù)且形如 n=22t（t+1=0 、1、2……）。簡單說，為費(fèi)馬素?cái)?shù)。 （3）邊數(shù) n具有n=2mp1p2p3...pk ，其中p1、p2、p3…pk為互不相同的費(fèi)馬素?cái)?shù)。 由高斯的結(jié)論，具有素?cái)?shù)p條邊的正多邊形可用尺規(guī)作圖的必要條件是p為費(fèi)馬數(shù)。由于我們現(xiàn)在得到的費(fèi)馬素?cái)?shù)只有前五個(gè)費(fèi)馬數(shù)，那么可用尺規(guī)作圖完成的正素?cái)?shù)邊形就只有3、5、17、257、65537。進(jìn)一步，可以做出的有奇數(shù)條邊的正多邊形也就只能通過這五個(gè)數(shù)組合而得到。這樣的組合數(shù)只有31種。而邊數(shù)為偶數(shù)的可尺規(guī)做出的正多邊形，邊數(shù)或是2的任意次正整數(shù)冪或與這31個(gè)數(shù)相結(jié)合而得到。
就這樣，正多邊形作圖問題與費(fèi)馬數(shù)極其密切地聯(lián)結(jié)在一起了！數(shù)學(xué)的一大魅力在于：看似全然無關(guān)的問題竟能以出人意料的方式彼此聯(lián)系在一起。透過“數(shù)學(xué)王子”高斯的杰出發(fā)現(xiàn)，人們確實(shí)可以從中充分領(lǐng)略到數(shù)學(xué)的這種魅力。事實(shí)上，正是兩者這種出乎意料的神秘結(jié)合，使人們對(duì)費(fèi)馬數(shù)有了更為持續(xù)不斷的興趣。
費(fèi)馬數(shù)研究的回顧與現(xiàn)狀 如上所述，對(duì)費(fèi)馬數(shù)的研究費(fèi)馬邁出了第一步。他給出正確的結(jié)論：前5個(gè)費(fèi)馬數(shù)都是素?cái)?shù)。然后，他做出猜想：所有的費(fèi)馬數(shù)都是素?cái)?shù)。
1732年，歐拉給出F5的素因子分解式：F5＝641×6 700 417，從而否定了費(fèi)馬的推斷。為了得出這一結(jié)果，歐拉還研究了費(fèi)馬數(shù)的性質(zhì)，證明了一個(gè)重要結(jié)論：當(dāng)n≥2時(shí)，費(fèi)馬數(shù)F5若有素因子，那么這一因子具有k×2n+1+1 的形式。這樣在尋找F5的因子時(shí)，就可直接排除掉許多不必進(jìn)一步檢驗(yàn)的無關(guān)的數(shù)值，從而大大減輕的運(yùn)算量。正是以此為依據(jù)，歐拉只對(duì)可能的因子進(jìn)行試除。最終找到了F5的第一個(gè)因子641，最終把F5進(jìn)行了完全分解。 1877年，數(shù)學(xué)家佩平得出一個(gè)重要的判據(jù)結(jié)果：費(fèi)馬數(shù)Fn是素?cái)?shù)，當(dāng)且僅當(dāng)F5整除3(Fn-1)/2+1 。這個(gè)結(jié)論對(duì)于檢驗(yàn)費(fèi)馬數(shù)的素性是很有效的。 1878年，盧卡斯改進(jìn)了歐拉的成果，證明費(fèi)馬數(shù)Fn若有素因子，那么這一因子具有k×2n+1+1 的形式。通過這一加強(qiáng)后的結(jié)論尋找Fn的素因子，從而判斷它是否是素?cái)?shù)就更為簡捷了。實(shí)際上，正是這一結(jié)論奠定了人們尋找大的費(fèi)馬合數(shù)的理論基礎(chǔ)。 1880年，著名數(shù)學(xué)家朗道給出F6的素因子分解式：F6＝247 177×67 280 421 310 721。 1905年，莫瑞漢德與韋斯坦證明F7是合數(shù)。1908年，這兩位數(shù)學(xué)家利用同樣的方法證明F8是合數(shù)。證明中使用了上述佩平檢驗(yàn)法則。 1957年，羅賓遜找到F1945的一個(gè)因子：5×21947+1 ，從而證明它是合數(shù)。 1977年，威廉姆找到F3310 的一個(gè)因子：5×3313+1 ，從而證明它是合數(shù)。1980年，人們找到F9948的一個(gè)因子：19×29450+1 ，從而證明它是合數(shù)。 1980年，哥廷汀證明 F17是合數(shù)。 1987年，楊和布爾證明F20是合數(shù)。 1980年，開勒證明了F9448是個(gè)合數(shù)，它有因子19×29450+1 。 1984年，開勒找到F23471 的一個(gè)因子：5×223473+1，從而證明它是一個(gè)合數(shù)。作為最大的費(fèi)馬合數(shù)這一紀(jì)錄保持了近十年。 1992年，里德學(xué)院的柯蘭克拉里和德尼亞斯用計(jì)算機(jī)證明了F22 是合數(shù)，這個(gè)數(shù)的十進(jìn)制形式有100萬位以上。這一證明曾被稱為有史以來為獲得一個(gè)“一位”答案（即“是－否”答案）而進(jìn)行的最長計(jì)算，總共用了1016次計(jì)算機(jī)運(yùn)算。 在對(duì)費(fèi)馬數(shù)的素因子分解方面，進(jìn)展要緩慢得多。 1971年，布里罕德和莫利遜用連分?jǐn)?shù)法，借助于電子計(jì)算機(jī)花了一個(gè)半小時(shí)的機(jī)時(shí)把F7分解為兩個(gè)質(zhì)因子的乘積，這兩個(gè)質(zhì)因子一個(gè)17位，一個(gè)22位。 1981年，布瑞特和普拉德利用蒙特卡羅方法在計(jì)算機(jī)上計(jì)算了兩小時(shí)，對(duì)F8進(jìn)行了分解，求得 F8＝1238926361552897與一個(gè)62位素?cái)?shù)的積。 1990年美國加州伯克萊分校的林斯特拉等人利用數(shù)域篩法（nFS）（并借助計(jì)算網(wǎng)絡(luò)）分解了 F9。它是2424833與一個(gè)148位數(shù)的積。
同年，澳大利亞國立大學(xué)的布瑞特用ECM算法（橢圓曲線法）分解了F10和F11 。迄今為止，F5 ~F11 ，是人們已經(jīng)完成標(biāo)準(zhǔn)素因子分解式的費(fèi)馬合數(shù)。n＝12、13、15、16、17、18、19、21、23時(shí)，對(duì)應(yīng)的費(fèi)馬數(shù)已找到部分因子。
最小的尚未完全分解的費(fèi)馬數(shù)是F12，它還有一個(gè)1187位的因子尚需要分解。n＝14、20、22、24時(shí)已經(jīng)證明是合數(shù)，但還沒有找到任何因子。尚未判定是合數(shù)還是質(zhì)數(shù)的最小費(fèi)馬數(shù)是F33。
費(fèi)馬數(shù)因子網(wǎng)絡(luò)搜尋計(jì)劃
隨著計(jì)算機(jī)的普及，個(gè)人電腦開始進(jìn)入千家萬戶。與之伴隨產(chǎn)生的是電腦的利用問題。越來越多的電腦處于閑置狀態(tài)，即使在開機(jī)狀態(tài)下CPU的潛力也遠(yuǎn)遠(yuǎn)不能被完全利用。而另一方面，需要巨大計(jì)算量的各種問題不斷涌現(xiàn)出來。因此在互聯(lián)網(wǎng)上開始出現(xiàn)了眾多的分布式計(jì)算計(jì)劃。所謂分布式計(jì)算是一門計(jì)算機(jī)學(xué)科，它研究如何把一個(gè)需要非常巨大的計(jì)算能力才能解決的問題分成許多小的部分，然后把這些部分分配給許多計(jì)算機(jī)進(jìn)行處理，最后把這些計(jì)算結(jié)果綜合起來得到最終的結(jié)果。 費(fèi)馬數(shù)因子網(wǎng)絡(luò)搜尋計(jì)劃是這種分布式計(jì)算計(jì)劃之一。在這項(xiàng)計(jì)劃中，人們打算借助網(wǎng)絡(luò)加速對(duì)費(fèi)馬數(shù)的研究。從比較小的費(fèi)馬數(shù) F12~ F23到一般大小的F24~ F1000再到巨大的費(fèi)馬數(shù)F1000 ~F50000
都包含在這一龐大的研究計(jì)劃之內(nèi)。正是通過這一網(wǎng)絡(luò)合作計(jì)劃，人們發(fā)現(xiàn)了許多有關(guān)費(fèi)馬數(shù)的新的結(jié)果。計(jì)算機(jī)出現(xiàn)之前，在近三百年的時(shí)間中，人們僅僅找到了16個(gè)費(fèi)馬素因子。而借助于計(jì)算機(jī)，借助于費(fèi)馬數(shù)因子網(wǎng)絡(luò)搜尋計(jì)劃，在短短的近半個(gè)世紀(jì)，人們已經(jīng)找到了234個(gè)費(fèi)馬素因子！
例如在2003年，人們就找到了8個(gè)費(fèi)馬因數(shù)。2003年10月10日，人們找到了具有746190位數(shù)的費(fèi)馬素因子：3×22478785+1 ，由此人們得到了截止目前為止最大的費(fèi)馬合數(shù) F2478782。2003年11月1日又宣布了一項(xiàng)最新成果：發(fā)現(xiàn)了一個(gè)新的費(fèi)馬素因子1054057×28300+1。這同時(shí)意味著又一個(gè)費(fèi)馬合數(shù)F8293的產(chǎn)生。
|
