TOPICS
Search

Poulet Number

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

A Poulet number is a Fermat pseudoprime to base 2, denoted psp(2), i.e., a composite number n such that

2^(n-1)=1 (mod n).

The first few Poulet numbers are 341, 561, 645, 1105, 1387, ... (OEIS A001567).

Pomerance et al. (1980) computed all 21853 Poulet numbers less than 25×10^9. The numbers less than 10^2, 10^3, ..., are 0, 3, 22, 78, 245, ... (OEIS A055550).

Pomerance showed that the count P_2(x) of Poulet numbers less than x satisfies, for sufficiently large x,

exp[(lnx)^(5/14)]<P_2(x)<xexp(-(lnxlnlnlnx)/(2lnlnx))

(Guy 1994).

A Poulet number all of whose divisors d satisfy d|2^d-2 is called a super-Poulet number. There are an infinite number of Poulet numbers which are not super-Poulet numbers. Shanks (1993) calls any positive integer satisfying 2^(n-1)=1 (mod n) (i.e., not limited to odd composite numbers) a Fermatian.

See also

Fermat Pseudoprime, Pseudoprime, Rotkiewicz Theorem, Super-Poulet Number

Explore with Wolfram|Alpha

References

Guy, R. K. Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 28-29, 1994.Pinch, R. G. E. "The Pseudoprimes up to 10^(13)." In Algorithmic Number Theory. Proceedings of the 4th International Symposium (ANTS-IV) Held at the Universiteit Leiden, Leiden, July 2-7, 2000 (Ed. W. Bosma). Berlin, Germany: Springer-Verlag, pp. 459-473, 2000. https://doi.org/10.1007/10722028_30.Pomerance, C.; Selfridge, J. L.; and Wagstaff, S. S. Jr. "The Pseudoprimes to 25·10^9." Math. Comput. 35, 1003-1026, 1980. https://doi.org/10.1090/s0025-5718-1980-0572872-7.Shanks, D. Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, pp. 115-117, 1993.Sloane, N. J. A. Sequences A001567/M5441 and A055550 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Poulet Number

Cite this as:

Weisstein, Eric W. "Poulet Number." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/PouletNumber.html

Subject classifications