費馬數的素性判斷

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

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

 

費馬數的素因子

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

 

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

如果取 a = 2,b = 1,則得出這樣的結論:費馬數 (Fermat Number) Fn = 2^(2n)+1 的因子必具有 k*2n+1+1 的型式。

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

例:F5 = (5*27+1)(52347*27+1) = 641*6700417

 

分解也不易

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

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

 

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

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