Strong pseudoprime

From Wikipedia, the free encyclopedia

In mathematics, a strong pseudoprime is a certain kind of natural number.

Contents

[edit] Formal definition

Formally, a composite number n := d · 2s + 1 is called a strong pseudoprime to base a iff one of the following conditions hold:

a^d\equiv 1\mod n
a^{d\cdot 2^r}\equiv -1\mod n\quad\mbox{ for some }0\leq r\leq(s-1)

It should be noted, however, that Guy uses a definition with only the first condition. Because not all primes pass that condition, this definition of 'strong pseudoprimes' resembles the primes less closely.

[edit] Properties of strong pseudoprimes

A strong pseudoprime to base a is always an Euler pseudoprime to base a (Pomerance, Selfridge, Wagstaff 1980), but not all Euler pseudoprimes are strong pseudoprimes. Some Fermat pseudoprimes and Carmichael numbers are also strong pseudoprimes.

As Monier and Rabin showed in 1980, a composite number n is a strong pseudoprime to at most one quarter of all bases <n; thus, there are no "strong Carmichael numbers", numbers that are strong pseudoprimes to all bases.

It can, however, be proven that there are infinitely many strong pseudoprimes to any base.

[edit] Examples

The first few strong pseudoprimes to base 2 are 2047, 3277, 4033, 4681, 8321, 15841, 29341, ... (sequence A001262 in OEIS); the first few strong pseudoprimes to base 3 are 121, 703, 1891, 3281, 8401, 8911, 10585, ... (sequence A020229 in OEIS).

[edit] References

  • C. Pomerance, J. L. Selfridge and Wagstaff, Jr., S. S., The pseudoprimes to 25 · 109, Math. Comp., 35:151 (1980) 1003-1026
  • Guy, R. K "Pseudoprimes. Euler Pseudoprimes. Strong Pseudoprimes." §A12 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 27-30, 1994.
Retrieved from "http://en.wikipedia.org../../../s/t/r/Strong_pseudoprime.html"
In other languages