费马数之猜想

伟大的科学家也会犯错误,连费马这位被誉为十七世纪最伟大的数学家也不例外。

费马三十岁时候得到图卢兹地方议会律师的职位。他一方面在做律师的工作,同时还利用业余时间从事数学研究。虽然费马一生中发表的著作不多,但他与同时代的许多一流数学家都有通信往来,并在当时有相当大的影响。例如,费马提出的费马大定理问题,一个永远的谜,带给后人的影响持续了350年之久。

费马对数学有很多的贡献,其中最突出的是他在数论方面奠基性的工作。而他所犯的错误也恰恰是在他最擅长的数论领域。

1640年费马在数论领域留下一个不可磨灭的足迹,他思考这样一个式子:2^(2^n) + 1 的值是否一定为素数。当n取0、1、2、3、4时,这个式子对应值分别为3、5、17、257、65 537 ,费马发现这五个数都是素数。

由此,费马提出一个猜想:形如2^(2^n) + 1的数一定为素数。由于F5太大(F5 =4 294 967 297),费马没有再往下继续进行验证。费马在给朋友的一封信中写道:“我已经发现形如2^(2^n) + 1的数永远为素数。很久以前我就向分析学家们指出了这个结论是正确的。” 费马同时坦白地承认,他自己未能找到一个完全的证明。 费马所研究的Fn=2^(2^n) + 1这种具有美妙形式的数,被人称之为费马数。就这样费马提出了一个猜想:所有费马数都一定是素数。费马的判断是正确的吗?

要验证费马的猜想并不容易。因为随着n的增大,Fn 迅速增大。比如对后人来说第一个需要检验的F5=4 294 967 297已经是一个十位数了。大约过了近百年,他的猜想被证明是错的。费马过分相信自己的直觉,做出了一个错误猜测。后来的研究的证明了费马不但是错的,而且是大错特错呢!

1729年12月1日,哥德巴赫在写给欧拉的一封信中问道:“费马认为所有形如2^(2^n) + 1的数都是素数,你知道这个问题吗?费马说他没能作出证明。据我所知,也没有其他任何人对这个问题作出过证明。” 这个问题引起了欧拉的兴趣。1732年,年仅25岁的欧拉验证发现了F5 =641×6 700 417,其中641=5×27+1,这一结果意味着F5 是一个合数。欧拉之后,又有人发现F6=27 477×67 280 421 310 721,也是合数。令人惊奇的是,陆续有数学家发现F77,F8……,直到F19以及许多n值很大的Fn全都是合数。

此后人们对更多的费马数进行了验证。计算机的发明使计算的过程大大简化了,计算机成为数学家研究费马数的有力工具。但即使如此,在所知的费马数中竟然没有再添加一个费马素数。迄今为止,费马素数除了被费马本人所证实的那五个外竟然没有再发现一个!因此人们开始猜想:在所有的费马数中,除了前五个是素数外,其他的都是合数。但是目前能判断它是素数还是合数的也只有几十个,除费尔马当年给出的5个外,至今尚未有新的素数发现。人们开始猜测:费马数是否只有有限个?除了那5个素数之外,是否再也没有了?这两个问题至今也没有解决,成为数学中的一个谜。 

费马数与尺规作图:出人意料的结合   

二千多年前,古希腊数学家曾深入研究过一类作图问题,即:如何利用尺规作内接正多边形。早在《几何原本》一书中,欧几里得就用尺规完成了圆内接正三边形、正四边形、正五边形,甚至正十五边形的作图问题。然而,似乎更容易完成的正7、9、11……边形却未能做出。让后来数学家尴尬的是,欧几里得之后的2000多年中,有关正多边形作图仍停留在欧几里得的水平上,未能向前迈进一步。 因此,我们可以想象得到,当1796年年仅19岁的高斯宣布他发现了正十七边形的作图方法时,会在数学界引起多么巨大的震憾了。  

不过,高斯的结果多少显得有些奇怪。他没有完成正七边形或正九边形等的作图,却偏偏隔下中间这一些直接完成了正十七边形。为什么第一个新做出的正多边形是正十七边形而不是正七、九边形呢?

在高斯的伟大发现之后,问题仍然存在:正七边形或正九边形等是否可尺规完成?或者更清楚地阐述这个问题:正多边形的边数具有什么特征时,它才能用尺规做出?   

在经过继续研究后,高斯最终在1801年对整个问题给出了一个漂亮的回答。高斯指出,如果仅用圆规和直尺,作圆内接正n边形,当n满足如下特征之一方可做出:   

(1)n=2m;( 为正整数)

(2)边数n为素数且形如 n=22tt+1=0 、1、2……)。简单说,为费马素数。

(3)边数 n具有n=2mp1p2p3...pk ,其中p1、p2、p3…pk为互不相同的费马素数。

由高斯的结论,具有素数p条边的正多边形可用尺规作图的必要条件是p为费马数。由于我们现在得到的费马素数只有前五个费马数,那么可用尺规作图完成的正素数边形就只有3、5、17、257、65537。进一步,可以做出的有奇数条边的正多边形也就只能通过这五个数组合而得到。这样的组合数只有31种。而边数为偶数的可尺规做出的正多边形,边数或是2的任意次正整数幂或与这31个数相结合而得到。  

就这样,正多边形作图问题与费马数极其密切地联结在一起了!数学的一大魅力在于:看似全然无关的问题竟能以出人意料的方式彼此联系在一起。透过“数学王子”高斯的杰出发现,人们确实可以从中充分领略到数学的这种魅力。事实上,正是两者这种出乎意料的神秘结合,使人们对费马数有了更为持续不断的兴趣。 

费马数研究的回顾与现状  

如上所述,对费马数的研究费马迈出了第一步。他给出正确的结论:前5个费马数都是素数。然后,他做出猜想:所有的费马数都是素数。  

1732年,欧拉给出F5的素因子分解式:F5=641×6 700 417,从而否定了费马的推断。为了得出这一结果,欧拉还研究了费马数的性质,证明了一个重要结论:当n≥2时,费马数F5若有素因子,那么这一因子具有k×2n+1+1 的形式。这样在寻找F5的因子时,就可直接排除掉许多不必进一步检验的无关的数值,从而大大减轻的运算量。正是以此为依据,欧拉只对可能的因子进行试除。最终找到了F5的第一个因子641,最终把F5进行了完全分解。

1877年,数学家佩平得出一个重要的判据结果:费马数Fn是素数,当且仅当F5整除3(Fn-1)/2+1 。这个结论对于检验费马数的素性是很有效的。

1878年,卢卡斯改进了欧拉的成果,证明费马数Fn若有素因子,那么这一因子具有k×2n+1+1 的形式。通过这一加强后的结论寻找Fn的素因子,从而判断它是否是素数就更为简捷了。实际上,正是这一结论奠定了人们寻找大的费马合数的理论基础。

1880年,著名数学家朗道给出F6的素因子分解式:F6=247 177×67 280 421 310 721。

1905年,莫瑞汉德与韦斯坦证明F7是合数。1908年,这两位数学家利用同样的方法证明F8是合数。证明中使用了上述佩平检验法则。

1957年,罗宾逊找到F1945的一个因子:5×21947+1 ,从而证明它是合数。

1977年,威廉姆找到F3310 的一个因子:5×3313+1 ,从而证明它是合数。1980年,人们找到F9948的一个因子:19×29450+1 ,从而证明它是合数。

1980年,哥廷汀证明 F17是合数。

1987年,杨和布尔证明F20是合数。

1980年,开勒证明了F9448是个合数,它有因子19×29450+1 。

1984年,开勒找到F23471 的一个因子:5×223473+1,从而证明它是一个合数。作为最大的费马合数这一纪录保持了近十年。

1992年,里德学院的柯兰克拉里和德尼亚斯用计算机证明了F22 是合数,这个数的十进制形式有100万位以上。这一证明曾被称为有史以来为获得一个“一位”答案(即“是-否”答案)而进行的最长计算,总共用了1016次计算机运算。

在对费马数的素因子分解方面,进展要缓慢得多。

1971年,布里罕德和莫利逊用连分数法,借助于电子计算机花了一个半小时的机时把F7分解为两个质因子的乘积,这两个质因子一个17位,一个22位。

1981年,布瑞特和普拉德利用蒙特卡罗方法在计算机上计算了两小时,对F8进行了分解,求得 F8=1238926361552897与一个62位素数的积。

1990年美国加州伯克莱分校的林斯特拉等人利用数域筛法(nFS)(并借助计算网络)分解了 F9。它是2424833与一个148位数的积。 

同年,澳大利亚国立大学的布瑞特用ECM算法(椭圆曲线法)分解了F10F11 。迄今为止,F5 ~F11 ,是人们已经完成标准素因子分解式的费马合数。n=12、13、15、16、17、18、19、21、23时,对应的费马数已找到部分因子。 

最小的尚未完全分解的费马数是F12,它还有一个1187位的因子尚需要分解。n=14、20、22、24时已经证明是合数,但还没有找到任何因子。尚未判定是合数还是质数的最小费马数是F33。 

费马数因子网络搜寻计划  

随着计算机的普及,个人电脑开始进入千家万户。与之伴随产生的是电脑的利用问题。越来越多的电脑处于闲置状态,即使在开机状态下CPU的潜力也远远不能被完全利用。而另一方面,需要巨大计算量的各种问题不断涌现出来。因此在互联网上开始出现了众多的分布式计算计划。所谓分布式计算是一门计算机学科,它研究如何把一个需要非常巨大的计算能力才能解决的问题分成许多小的部分,然后把这些部分分配给许多计算机进行处理,最后把这些计算结果综合起来得到最终的结果。

费马数因子网络搜寻计划是这种分布式计算计划之一。在这项计划中,人们打算借助网络加速对费马数的研究。从比较小的费马数 F12~ F23到一般大小的F24~ F1000再到巨大的费马数F1000 ~F50000 都包含在这一庞大的研究计划之内。正是通过这一网络合作计划,人们发现了许多有关费马数的新的结果。计算机出现之前,在近三百年的时间中,人们仅仅找到了16个费马素因子。而借助于计算机,借助于费马数因子网络搜寻计划,在短短的近半个世纪,人们已经找到了234个费马素因子!  

例如在2003年,人们就找到了8个费马因数。2003年10月10日,人们找到了具有746190位数的费马素因子:3×22478785+1 ,由此人们得到了截止目前为止最大的费马合数 F2478782。2003年11月1日又宣布了一项最新成果:发现了一个新的费马素因子1054057×28300+1。这同时意味着又一个费马合数F8293的产生。