# Fermat pseudoprime

From Citizendium, the Citizens' Compendium

A composite number is called a **Fermat pseudoprime** to a natural base , which is coprime to , if .

## Contents

## Restriction

It is sufficient that the base satisfies because every odd number satisfies for ^{[1]}.

If is a Fermat pseudoprime to base then is a Fermat pseudoprime to base for every integer .

## Odd Fermat pseudoprimes

To every odd Fermat pseudoprime exist an even number of bases . Every base has a cobase .

Examples:

- 15 is a Fermat pseudoprime to the bases 4 and 11

- 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.

## References and notes

- ↑ Richard E. Crandall and Carl Pomerance: Prime Numbers: A Computational Perspective. Springer-Verlag, 2001, page 132, Theorem 3.4.2.

## Further reading

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