# Strong pseudoprime

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Main Article
Discussion
Related Articles  [?]
Bibliography  [?]
Citable Version  [?]

This editable Main Article is under development and subject to a disclaimer.

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

A composite number ${\displaystyle \scriptstyle q=d\cdot 2^{s}+1}$ (where ${\displaystyle \scriptstyle d\ }$ is odd) is a strong pseudoprime to a base ${\displaystyle \scriptstyle a\ }$ if:

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

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 ${\displaystyle \scriptstyle q\ }$ is pseudoprime to a base ${\displaystyle \scriptstyle a\ }$ in ${\displaystyle \scriptstyle a^{d}\equiv 1{\pmod {q}}}$, than ${\displaystyle \scriptstyle q\ }$ is pseudoprime to a base ${\displaystyle \scriptstyle a'=q-a\ }$ in ${\displaystyle \scriptstyle a'^{d}\equiv -1{\pmod {q}}}$ and vice versa.
• There exist Carmichael numbers that are also strong pseudoprimes.