費馬數猜想
法國業餘數學王子費馬 (Pierre de Fermat 1601-1665)
(照片取自「The MacTutor History of Mathematics Achieve」http://www-gap.dcs.st-and.ac.uk/~history/ )
費馬數的故事
法國數學家費馬 (Pierre de Fermat 1601-1665) 也曾在數論 (Number Theory),等別是素數上花過不少心力。
他以為若 m=pk ,其中 p 是奇數則有
2m+1 = 2pk+1 = (2k)p-1 = (2k+1) * (2k(p-1) - 2k(p-2) + 2k(p-3) - ...... - 2k+1) ,
上式後方的括號內的東西不太重要,但前方括號內的東西告訴我們 2m+1 必可被 2k+1 整除。
因此要使 2m+1 是素數,則 m 不可含有奇因子,於是費馬取 m = 2n ,從而,
Fn = 2m+1 = 2^(2n)+1,但這是不是全是素數呢?費馬作了下列測試:
F0 = 3, F1 = 5, F2 = 17, F3 = 257, F4 = 65537 全是素數。他在 1640 年給梅森 (Marin Mersenne 1588-1648) 的一封信中提到,他相信形如 Fn = 2^(2n)+1 的數全是素數,但他不能給出証明,這便是著名的費馬數猜想 (Fermat Number Conjecture)。我們現稱這類型的數為費馬數 (Fermat Number),這類型的素數為費馬素數 (Fermat Prime) 。
在費馬死後的 67年,即1732年,瑞士數學家歐拉 (Leonhard Euler 1707-1783) 對費馬數進行了深入的分析,發現 F5 = 641 * 6700417 其實是一個合數,從而推翻了費馬數猜想,這亦是人們所知費馬一生中惟一的錯誤。其實在費馬的年代,是沒有計算機的,要驗証這樣的「大數」的素性可不容易,但費馬卻碰到了一個這樣「快大」的數列,n 不到 5 已是上億的「大數」。可憐的費馬只好在小的 n 值作研究,為費馬數立論。可惜他怎麼樣也想不到,他走多一步便不會立了這一個錯的猜想了。
歐拉不是以試除法去判斷 F5 的素性,而是這樣証明的:
設 a = 27 , b = 5,
則 a-b3 = 3,1+ab-b4 = 24,
F5 = (2a)4+1
= (24)(a4)+1
= (1+ab-b4)(a4)+1
= (1+ab)(a4)+[1- (a4)(b4) ]
= (1+ab)(a4)+(1-ab)(1+ab)(1+a2b2)
=(1+ab)[a4+(1-ab)(1+a2b2)]
式中 1+ ab = 641,而 a4+(1-ab)(1+a2b2) = 6700417 了。
1880年法國數學家盧卡斯 (Edouard Lucas 1842-1891) 証明了 F6 是一個合數。後來更有人指出
F6 = 274177 * 67280421310721
之後數學家不斷尋找更新和更大的費馬數,可惜它們不是合數,便是未知素性的。故至今除了開首的幾個費馬素數以外,並未有新的費馬素數,數學家傾向支持費馬素數有限個的說法,甚至有數學家斷言費馬素數也只得開始的那幾個,但此等也不過是一猜想而已。數學家因而轉移去研究費馬合數 (Fermat Composite) 的分解,希望在費馬數因子 (Fermat Number Divisor) 中找到更多的素數。
費馬數的特性
其實費馬數也有一些奇怪的特性,其中有一個是這樣的:
除了 F0 和 F1 以外,其他的費馬數的個位全是 7 ,單從 F2 = 17, F3 = 257, F4 = 65537 並無反例,實際也不會有。因為 2^(22) = 16 = 6 的個位是 6 ,而 2^(23) = 256 的個位也是 6 , 2^(24) = 65536 的個位也是 6,一個數的個位是 6 ,其平方的個位也是 6 。所以之後的費馬數的個位全是 7 。
另外,Fn+1 = Fn *Fn-1 *... *F0 + 2,用歸納法証明不太難,留給我們親愛的讀者吧。
1801年,德國大數學家高斯 (Carl Friedrich Gauss 1777-1855) 在其《算術研究》中証明了,我們可用圓規直尺作圖正 n 邊形 (或圓周等分 n 份)中的 n 值的素因子分解式中只可有 2 和費馬素數,而費馬素數的指數 (Index) 則不可多於 1。或說可用圓規直尺作圖正奇數多邊形 (或圓周等分奇數份) 中的奇數必為費馬素數或其乘積。現在已証的費馬素數僅 5 個,我們不難証明可用圓規直尺作圖正奇數多邊形 (或圓周等分奇數份)合 25-1 = 31 個)。
下表列寫可作正奇數多邊形的 31 個可能值:
1 |
3 |
= |
3 |
2 |
5 |
= |
5 |
3 |
15 |
= |
3*5 |
4 |
17 |
= |
17 |
5 |
51 |
= |
3*17 |
6 |
85 |
= |
5*17 |
7 |
255 |
= |
3*5*17 |
8 |
257 |
= |
257 |
9 |
771 |
= |
3*257 |
10 |
1285 |
= |
5*257 |
11 |
3855 |
= |
3*5*257 |
12 |
4369 |
= |
17*257 |
13 |
13107 |
= |
3*17*257 |
14 |
21845 |
= |
5*17*257 |
15 |
65535 |
= |
3*5*17*257 |
16 |
65537 |
= |
65537 |
17 |
196611 |
= |
3*65537 |
18 |
327685 |
= |
5*65537 |
19 |
983055 |
= |
3*5*65537 |
20 |
1114129 |
= |
17*65537 |
21 |
3342387 |
= |
3*17*65537 |
22 |
5570645 |
= |
5*17*65537 |
23 |
16711935 |
= |
3*5*17*65537 |
24 |
16843009 |
= |
257*65537 |
25 |
50529027 |
= |
3*257*65537 |
26 |
84215045 |
= |
5*257*65537 |
27 |
252645135 |
= |
3*5*257*65537 |
28 |
286331153 |
= |
17*257*65537 |
29 |
858993459 |
= |
3*17*257*65537 |
30 |
1431655765 |
= |
5*17*257*65537 |
31 |
4294967295 |
= |
3*5*7*257*65537 |
要真的用圓規直尺作一正 4294967295 邊形,只是理論可行,相信沒人會作這樣的工作。 赫爾梅斯 (Hermes) 教授為了嘗試作正 65537 邊形已花了他十年光景了,據說他的手稿可裝滿一手提箱。
參考文獻及網址:
Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, pp. 68-69 and 94-95, 1987.
Conway, J. H. and Guy, R. K. "Fermat's Numbers." In The Book of Numbers. New York: Springer-Verlag, pp. 137-141, 1996.
Weisstein, E. W. "Fermat Number." From MathWorld. http://mathworld.wolfram.com/FermatNumber.html.