Strong pseudoprime

From Wikipedia, the free encyclopedia

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

1 Formal definition
2 Properties of strong pseudoprimes
3 Examples
4 References

[edit] 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.

[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).