Fermat pseudoprime

A composite number $\scriptstyle q\$ is called a Fermat pseudoprime to a natural base $\scriptstyle a\$, which is coprime to $\scriptstyle q\$, if $\scriptstyle a^{q-1}\equiv 1{\pmod {q}}$.

Restriction

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

If $\scriptstyle q\$ is a Fermat pseudoprime to base $\scriptstyle a\$ then $\scriptstyle n\$ is a Fermat pseudoprime to base $\scriptstyle b\cdot q+a$ for every integer $\scriptstyle 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 pseudoprimes, Carmichael numbers, Fibonacci pseudoprimes and Lucas pseudoprimes, are Fermat pseudoprimes.

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 the Fermat pseudoprimes between 15 and 4997