Strong pseudoprime

A strong Pseudoprime is an Euler pseudoprime with a special property:

If a composite Number $\scriptstyle q\$ is factorable in $\scriptstyle q=d\cdot 2^{s}$, whereby $\scriptstyle d\$ an odd number is, then is $\scriptstyle q\$ a strong Pseudoprime to a base $\scriptstyle a\$ if:

• $a^{d}\equiv 1{\pmod {q}}$

or

• $a^{d\cdot 2^{r}}\equiv -1{\pmod {q}}$ if $0\leq r<s-1$

The first condition is stronger

Properties

• Every strong pseudoprime is also an Euler pseudoprime
• Every strong pseudoprime is odd, because every Euler pseudoprime is odd.
• If a strong pseudoprime $\scriptstyle q\$ is pseudoprime to a base $\scriptstyle a\$ in $\scriptstyle a^{d}\equiv 1{\pmod {q}}$, than $\scriptstyle q\$ is pseudoprime to a base $\scriptstyle a'=q-a\$ in $\scriptstyle a'^{d}\equiv -1{\pmod {q}}$ and versa vice.
• It exist an Intersection between the set of strong pseudoprimes and the set of Carmichael numbers

Further reading

• Richard E. Crandall and Carl Pomerance. Prime Numbers: A Computational Perspective. Springer-Verlag, 2001, ISBN 0-387-25282-7
• Paolo Ribenboim. The New Book of Prime Number Records. Springer-Verlag, 1996, ISBN 0-387-94457-5

Links

• Table of strong pseudoprimes between 49 and 1393