|
We are creating the world's most trusted encyclopedia and knowledge base.
|
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
- Paolo Ribenboim: The New Book of Prime Number Records. Springer-Verlag, 1996, ISBN 0-387-94457-5
