Fermat pseudoprime

A composite number $q\$ is called Fermat pseudoprime to a natural base $a\$, coprime to $q\$, so that $a^{q-1}\equiv 1{\pmod {q}}$

Restriction

It is sufficient, that the base $a\$ satisfy $2\leq a\leq q-2$ because every odd number $q\$ satisfy for $a=q-1\$ that $a^{q-1}\equiv 1{\pmod {q}}$

If $q\$ is a Fermat pseudoprime to base $a\$, then $n\$ is a Fermat pseudoprime to base $b\cdot q+a$ for every integer $b\geq 0$

Odd Fermat pseudoprimes

To every odd Fermat pseudoprime $\scriptstyle q\$ exist an even number of bases $\scriptstyle a\$. Every base $\scriptstyle a\$ has a cobase $\scriptstyle a'=q-a\$

Examples

15 is a Fermat pseudoprime to the bases 4 and 15

49 is a Fermat pseudoprime to the bases 18, 19, 30 and 31

Properties

Most of the Pseudoprimes, like Euler pseudoprime, Carmichael number, Fibonacci pseudoprime and Lucas pseudoprime, are Fermat pseudoprimes.

Further reading

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