費馬數的素性判斷

俄國數學家佩爾武申 (Ivan Mikheevich Pervusin 1829-1900)

(照片取自「The MacTutor History of Mathematics Achieve」http://www-gap.dcs.st-and.ac.uk/~history/ )

　

費馬數的素因子

誰人也估不到費馬素數 (Fermat Prime) ，即型如 F_n = 2^(2ⁿ)+1的素數，竟和圓規直尺作圖 (Ruler-and-Compass Construction) 有關。1801年，德國大數學家高斯 (Carl Friedrich Gauss 1777-1855) 在其《算術研究》(Disquisitiones Arithmeticae) 中證明了，當 n 是費馬素數或不同的費馬素數乘積時，則可用圓規直尺作圖正 n 邊形 (或圓周等分 n 份) (可參看另文《費馬數猜想》) ，後來更有人主張費馬素數和費馬最後定理 (Fermat's Last Theorem, xⁿ + yⁿ = zⁿ ，當 n 大於 2 時沒有非零整數解) 連上關係，證明了 x^p + y^p = z^p ，當 p 為費馬素數時沒有正整數解。費馬數 (Fermat Number) 如此奇妙，判斷其素性 (Primality) 更顯重要。

　

大約在1770年，歐拉 (Leonhard Euler 1707-1783) 證明了，如果 a 與 b 是互素的整數，則 a^(2ⁿ) + b^(2ⁿ) 的因子是 2 或具有 k*2ⁿ⁺¹+1 的型式。

如果取 a = 2，b = 1，則得出這樣的結論：費馬數 (Fermat Number) F_n = 2^(2ⁿ)+1 的因子必具有 k*2ⁿ⁺¹+1 的型式。

1877年，法國數學家盧卡斯 (Edouard Lucas 1842-1891) 改進歐拉上述結果，證明了上式中的 k 必是偶數。即費馬數 F_n 的每個因子都是以 k*2ⁿ⁺²+1 的型式存在，其中 k 為正整數，這是盧卡斯 - 歐拉定理 (Lucas - Euler Theorem)。

例：F₅ = (5*2⁷+1)(52347*2⁷+1) = 641*6700417

　

分解也不易

其實要完全分解費馬數可不是一件容易的事，隨著 n 增大，F_n 急速增大，現在完全分解只在 n 不多於 11 以內。在1878年，俄國數學家佩爾武申 (Ivan Mikheevich Pervusin 1829-1900) 家證明了 F₂₃ ，一個有 2525223個數位的整數，有素因子 5*2²⁵+1 。更大的 F₃₆ 遠超 200 億個數位，1886年，德國數學家西爾霍夫 (Paul Seelhoff 1829-1896) 證明了這巨數有因子 10*2³⁸+1。由此可見判斷費馬數的素性是如何艱鉅的。直到 2003年，人們共發現了 214 個費馬合數 (Fermat Composite) ，其中最大的是 F_2145353 ，而其素因子 3* 2^2145353+1，是一個有 645816 個數位的素數，亦是當時所知最大的非梅森素數，單是一素因子已如此巨大，原本的費馬數更是大得嚇人 (粗略估計該數達 7*10¹⁹⁴⁴⁰⁹ 個數位之多)。但數學家們卻沒有新發現的費馬素數。而最小一個未能分辨是素數還是合數 的費馬數是 n=33，到底這 2585827972 個數位的怪物是素數還是合數，暫不知曉，但相信不用多久這記錄又得改寫。

可參考另《費馬數的素因子》，文中列寫了一些已分解或局部分解的費馬合數和其素因子。

　

英國數學家哈代 (Godfrey Harold Hardy 1877-1947) 認為費馬素數個數有限，而美國數學家塞爾弗里奇 (John L. Selfridge 1953- ) 更激進的認為費馬素數就只有五個。在這新的費馬數猜想的角力中，人們漸轉向支持有限個費馬素數的說法，去尋求費馬合數的分解。

但尋找費馬素數的路途不見平坦，於是數學家唯有另闢門徑，有的把費馬數的定義擴展，吸納更多的素數，即所謂的「廣義費馬數」(Generalized Fermat Number)；有的在費馬數的定義基礎下開展新的數種，如「卡倫數」 (Cullen Number) 或「伍德爾數」 (Woodall Number)；亦有的向費馬數的因子入手，即所謂的「普羅絲數」 (Proth Number) 。本章及接後一章會有多篇文章介紹相關的素數，歡迎參看。