Strong pseudoprime

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

Formal definition

Formally, a composite number n := d · 2^s + 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.

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.

Examples

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

References

• C. Pomerance, J. L. Selfridge and Wagstaff, Jr., S. S., The pseudoprimes to 25 · 10⁹, Math. Comp., 35:151 (1980) 1003-1026