费马数研究的回顾与现状

费马数研究的回顾与现状

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

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

1877年，数学家佩平得出一个重要的判据结果：费马数Fn是素数，当且仅当F₅整除。这个结论对于检验费马数的素性是很有效的。

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

1880年，著名数学家朗道给出F₆的素因子分解式：F₆＝247177×67280421310721。

1905年，莫瑞汉德与韦斯坦证明F₇是合数。1908年，这两位数学家利用同样的方法证明F₈是合数。证明中使用了上述佩平检验法则。1957年，罗宾逊找到F₁₉₄₅的一个因子：5×21947＋1，从而证明它是合数。1977年，威廉姆找到F₃₃₁₀的一个因子：5×3313＋1，从而证明它是合数。1980年，人们找到F₉₉₄₈的一个因子：19×29450＋1，从而证明它是合数。1980年，哥廷汀证明F₁₇是合数。1987年，杨和布尔证明F₂₀是合数。1980年，开勒证明了F₉₄₄₈是个合数，它有因子19×29450＋1。1984年，开勒找到F₂₃₄₇₁的一个因子：5×223473＋1，从而证明它是一个合数。作为最大的费马合数这一纪录保持了近十年。1992年，里德学院的柯兰克拉里和德尼亚斯用计算机证明了F₂₂是合数，这个数的十进制形式有100万位以上。这一证明曾被称为有史以来为获得一个“一位”答案（即“是－否”答案）而进行的最长计算，总共用了10¹⁶次计算机运算。

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

1971年，布里罕德和莫利逊用连分数法，借助于电子计算机花了一个半小时的机时把F₇分解为两个质因子的乘积，这两个质因子一个17位，一个22位。1981年，布瑞特和普拉德利用蒙特卡罗方法花两小时机上时间，对F₈进行了分解，求得F₈＝1238926361552897与一个62位素数的积。1990年美国加州伯克莱分校的林斯特拉等人利用数域筛法（nFS）（并借助计算网络）分解了F₉。它是2424833与一个148位数的积。同年，澳大利亚国立大学的布瑞特用ECM算法（椭圆曲线法）分解了F₁₀和F₁₁。迄今为止，F₅～F₁₁，是人们已经完成标准素因子分解式的费马合数。n＝12、13、15、16、17、18、19、21、23时，对应的费马数已找到部分因子。因此，最小的尚未完全分解的费马数是F₁₂，它还有一个1187位的因子尚需要分解。n＝14、20、22、24时已经证明是合数，但还没有找到任何因子。尚未判定是合数还是质数的最小费马数是F₃₃。