Fermat pseudoprime

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

Restriction

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

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

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