費馬數猜想
法國數學家費馬 (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), 特別是素數 (Prime Number) 上花過不少心力。
他以為若 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,這 被稱作二乘方定理 (Theorem of Binary Powers) 的公式是不是會全給出素數呢?費馬作了下列測試:
F0 = 3, F1 = 5, F2 = 17, F3 = 257, F4 = 65537 全是素數。他相信型如 Fn = 2^(2n)+1 的數全是素數, 並在 1650 年發表成一猜想,但他不能給出證明,這便是著名的費馬數猜想 (Fermat Number Conjecture)。我們現稱這類型的數為費馬數 (Fermat Number),這類型的素數為費馬素數 (Fermat Prime) 。
在費馬死後的 67年,即 1732年,瑞士數學家歐拉 (Leonhard Euler 1707-1783) 對費馬數進行了深入的分析,發現 F5 = 641 * 6700417 其實是一個合數,從而推翻了費馬數猜想,這亦是人們所知費馬一生中惟一的錯誤。其實在費馬的年代,是沒有計算機的,要驗證這樣的「大數」的素性 (Primality) 可不容易,但費馬卻碰到了一個這樣「快大」的數列,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,用數學歸納法 (Mathematical Induction) 證明不太難,這工作不如留給我們親愛的讀者試試吧。
1801年,德國大數學家高斯 (Carl Friedrich Gauss 1777-1855) 在其《算術研究》(Disquisitiones Arithmeticae) 中證明了,我們可用圓規直尺作圖 (Ruler-and-Compass Construction) 正 n 邊形 (或圓周等分 n 份)中的 n 值的素因子分解式 (Prime Factorization) 中只可有 2 和費馬素數,而費馬素數的指數則不可多於 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 邊形,只是理論可行,相信沒人會作這樣的工作。
比亞邦特素數
比亞邦特素數 (Pierpont Prime) 是指型如 2a * 3b + 1 的素數。
下表列出十萬以內的比亞邦特素數:
比亞邦特素數 | a | b | 比亞邦特素數 | a | b | 比亞邦特素數 | a | b | 比亞邦特素數 | a | b | 比亞邦特素數 | a | b | ||||
2 | 0 | 0 | 3 | 1 | 0 | 5 | 2 | 0 | 7 | 1 | 1 | 13 | 2 | 1 | ||||
17 | 4 | 0 | 19 | 1 | 2 | 37 | 2 | 2 | 73 | 3 | 2 | 97 | 5 | 1 | ||||
109 | 2 | 3 | 163 | 1 | 4 | 193 | 6 | 1 | 257 | 8 | 0 | 433 | 4 | 3 | ||||
487 | 1 | 5 | 577 | 6 | 2 | 769 | 8 | 1 | 1153 | 7 | 2 | 1297 | 4 | 4 | ||||
1459 | 1 | 6 | 2593 | 5 | 4 | 2917 | 2 | 6 | 3457 | 7 | 3 | 3889 | 4 | 5 | ||||
10369 | 7 | 4 | 12289 | 12 | 1 | 17497 | 3 | 7 | 18433 | 11 | 2 | 39367 | 1 | 9 | ||||
52489 | 3 | 8 | 65537 | 16 | 0 | (OEIS A113412) |
當然費馬素數亦是比亞邦特素數的一個子集 (Subset),其中取 b=0、a 為 2 的方冪而已。
除此以外,比亞邦特素數和費馬素數還有一樣東西連上關係,那便是作正多邊形的圖了。原來若我們容許以圓規直尺和三等分角 (Angle-trisector) 作圖的話,能作的正多邊形的邊數為
2s * 3t * p1 * p2 * p3 * ...
式中的 p1 、 p2 、 p3 、 ... 便是比亞邦特素數。
所謂三等分角,即把任意大小的角等分為三份,這和平分角 (Angle-bisector) 不一樣,是不可以圓規直尺在有限步驟內完成的。當然原來可以用圓規直尺作的正多邊形亦在上式中,所以我們便有「費馬素數亦是比亞邦特素數的一個子集」這一結論了。
比亞邦特素數和費馬素數有一點不盡相同,費馬素數個數似乎有限,但比亞邦特素數卻未必相同了,看看下表:
n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
小於 10n 的比亞邦特素數個數 | 4 | 10 | 18 | 25 | 32 | 42 | 50 | 58 | 65 |
我們發現大約當 n 增加一倍時,比亞邦特素數的個數亦增加一倍,但這是巧合還是必然的呢?還是一個謎。在 2010 年前,已知最大的比亞邦特素數為 3*25082306+1,該數達 1529928 位之大。
參考文獻及網址:
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.
Weisstein, E. W. "Pierpont Prime." From MathWorld. http://mathworld.wolfram.com/PierpontPrime.html.
吳鶴齡 , 幻方與素數 , 北京 : 科學出版社 , p. 157 , 2008