Fermat Pseudoprime
المؤلف:
Hoffman, P.
المصدر:
The Man Who Loved Only Numbers: The Story of Paul Erdős and the Search for Mathematical Truth. New York: Hyperion
الجزء والصفحة:
...
24-1-2021
1573
Fermat Pseudoprime
A Fermat pseudoprime to a base 
, written psp(
), is a composite number 
such that 
, i.e., it satisfies Fermat's little theorem. Sometimes the requirement that 
must be odd is added (Pomerance et al. 1980) which, for example would exclude 4 from being considered a psp(5).
psp(2)s are called Poulet numbers or, less commonly, Sarrus numbers or Fermatians (Shanks 1993). The following table gives the first few Fermat pseudoprimes to some small bases 
.
 |
OEIS |
 -Fermat pseudoprimes |
| 2 |
A001567 |
341, 561, 645, 1105, 1387, 1729, 1905, ... |
| 3 |
A005935 |
91, 121, 286, 671, 703, 949, 1105, 1541, 1729, ... |
| 4 |
A020136 |
15, 85, 91, 341, 435, 451, 561, 645, 703, ... |
| 5 |
A005936 |
4, 124, 217, 561, 781, 1541, 1729, 1891, ... |
If base 3 is used in addition to base 2 to weed out potential composite numbers, only 4709 composite numbers remain 
. Adding base 5 leaves 2552, and base 7 leaves only 1770 composite numbers.
The following table gives the number of Fermat pseudoprimes to various small bases less than 10, 
, 
, ....
| base(s) |
OEIS |
Fermat pseudoprimes less than 10,  , ... |
| 2 |
A055550 |
0, 0, 3, 22, 78, 245, 750, 2057, ... |
| 2, 3 |
A114246 |
0, 0, 0, 7, 23, 66, 187, 485, ... |
| 2, 3, 5 |
A114248 |
0, 0, 0, 4, 11, 36, 95, 257, ... |
| 2, 3, 5, 7 |
A114250 |
0, 0, 0, 0, 3, 19, 63, 175, ... |
| 3 |
A114245 |
0, 1, 6, 23, 78, 246, 760, 2155, ... |
| 5 |
A114247 |
1, 1, 5, 20, 73, 248, 745, 1954, ... |
| 7 |
A114249 |
1, 2, 6, 16, 73, 234, 659, 1797, ... |
REFERENCES:
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 
." Math. Comput. 35, 1003-1026, 1980. https://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."
الاكثر قراءة في نظرية الاعداد
اخر الاخبار
اخبار العتبة العباسية المقدسة
