Fermat pseudoprime

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

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

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

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

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