主題
Search

費馬偽素數

DOWNLOAD Mathematica Notebook下載 Wolfram Notebook

以 a 為底的費馬偽素數，記作 psp(a)，是一個合數 n，使得 a^(n-1)=1 (mod n)，即，它滿足費馬小定理。 有時會新增 n 必須是 奇數 的要求（Pomerance et al. 1980），例如，這將排除 4 被認為是 psp(5)。

psp(2) 被稱為 Poulet 數，或者較少見的，Sarrus 數或 Fermatians (Shanks 1993)。 下表給出了一些小底數 b 的前幾個費馬偽素數。

bOEISb-費馬偽素數
2A001567341, 561, 645, 1105, 1387, 1729, 1905, ...
3A00593591, 121, 286, 671, 703, 949, 1105, 1541, 1729, ...
4A02013615, 85, 91, 341, 435, 451, 561, 645, 703, ...
5A0059364, 124, 217, 561, 781, 1541, 1729, 1891, ...

如果除了基數 2 之外還使用基數 3 來篩選潛在的合數，則僅剩下 4709 個合數 <25×10^9。 新增基數 5 剩下 2552 個，而基數 7 僅剩下 1770 個合數。

下表給出了對於小於 10 的各種小底數，小於 10^2, 10^3, .... 的費馬偽素數的數量。

底數OEIS小於 10 的費馬偽素數，10^2, ...
2A0555500, 0, 3, 22, 78, 245, 750, 2057, ...
2, 3A1142460, 0, 0, 7, 23, 66, 187, 485, ...
2, 3, 5A1142480, 0, 0, 4, 11, 36, 95, 257, ...
2, 3, 5, 7A1142500, 0, 0, 0, 3, 19, 63, 175, ...
3A1142450, 1, 6, 23, 78, 246, 760, 2155, ...
5A1142471, 1, 5, 20, 73, 248, 745, 1954, ...
7A1142491, 2, 6, 16, 73, 234, 659, 1797, ...

另請參閱

Carmichael 數, 費馬小定理, Poulet 數, 偽素數

使用 探索

參考文獻

Hoffman, P. The Man Who Loved Only Numbers: The Story of Paul Erdős and the Search for Mathematical Truth. New York: Hyperion, p. 182, 1998.Pomerance, C.; Selfridge, J. L.; and Wagstaff, S. S. Jr. "The Pseudoprimes to 25·10^9." Math. Comput. 35, 1003-1026, 1980. http://mpqs.free.fr/ThePseudoprimesTo25e9.pdf.Shanks, D. Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, p. 115, 1993.Sloane, N. J. A. Sequences A001567/M5441, A005935/M5362, A005936/M3712, A020136, A055550, A114245, A114246, A114247, A114248, A114249, and A114250 in "The On-Line Encyclopedia of Integer Sequences."

在 上被引用

費馬偽素數

請這樣引用

Weisstein, Eric W. “費馬偽素數。” 來自 Web 資源。 https://mathworld.tw/FermatPseudoprime.html

主題分類