普羅絲素數

尋找費馬素數 (Fermat Prime) ,即型如 Fn = 2^(2n)+1的素數的路途未見寸進,更有數學家對是否存在更多的費馬素數有所質疑,於是有一些數學家轉向尋找費馬數因子 (Fermat Number Divisor)。

普羅絲素數 (Proth Prime) 是指型如 N = k*2n + 1 而 2n > k 的素數 (Prime Number),而費馬數因子可以說是普羅絲素數的一類。 還記得數學家歐拉 (Leonhard Euler 1707-1783) 把費馬數 F5 分解成 F5 = 641*6700417 ,當中的 641 正是普羅絲素數,但 6700417 = 1+ 52347 * 27 , 且 52347 > 27 ,所 以 6700417 不是普羅絲素數。

想一想,若我不作 2n > k 這個規限會怎樣呢?任何偶數均可寫成 k*2n 的型式,其中 k 為奇數。或者說句,任何奇素數也可寫成 k*2n + 1 的樣子,即任何奇素數 (Odd Prime) 是普羅絲素數了。

 

那麼什麼是普羅絲素數呢?

根據普羅絲定理 (Proth's Theorem) ,若 a (N-1)/2 = -1 (mod N) ,則 N 是一素數,因而得名。關於普羅絲定理的介紹,可參看《不斷改進的方法》一文。如 3 = 1*21 + 1 、 5 = 1*22 + 1 、 13 = 3*22 + 1 、 17 = 2*23 + 1 、 41 = 5*23 + 1 、 ...... (OEIS A080076)

法國人加洛特 (Yves Gallot 1966- ) 更創作了一搜尋普羅絲素數的程式,名為 Proth.exe 免費供人使用。

這程式對尋找普羅絲素數和分解費馬數上起了很大的作用。而加洛特本人亦建立了一個網站,整理和匯報關於費馬數及各類由費馬數而生的素數尋找等工作的進度。欲知詳情,可至 Proth Search Page .

 

參考文獻及網址:

Ballinger, R. "Proth Search Page." http://www.prothsearch.net/.

Caldwell, C. K. "The Top Twenty: Proth." http://primes.utm.edu/top20/page.php?id=66.

McNamara, J. and Mills, M. "Factoring of Proth Numbers." http://www.fidn.org/proth1.html.

Weisstein, E. W. "Proth Prime." From MathWorld http://mathworld.wolfram.com/ProthPrime.html.