Fermat pseudoprime: Difference between revisions
Jump to navigation
Jump to search
imported>Karsten Meyer mNo edit summary |
imported>Louise Valmoria (adding subpage template) |
||
| Line 1: | Line 1: | ||
{{subpages}} | |||
A composite number ''n'' is called '''Fermat pseudoprime''' to a natural base ''a'', coprime to n, so that <math>a^{n-1} \equiv 1 \pmod n</math> | A composite number ''n'' is called '''Fermat pseudoprime''' to a natural base ''a'', coprime to n, so that <math>a^{n-1} \equiv 1 \pmod n</math> | ||
| Line 16: | Line 18: | ||
* [[Richard E. Crandall]] and [[Carl Pomerance]]: Prime Numbers. A Computational Perspective. Springer Verlag, ISBN 0-387-25282-7 | * [[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 | * [[Paolo Ribenboim]]: The New Book of Prime Number Records. Springer Verlag, 1996, ISBN 0-387-94457-5 | ||
Revision as of 11:41, 6 December 2007
A composite number n is called Fermat pseudoprime to a natural base a, coprime to n, so that
Restriction
It is sufficient, that the base a satisfy because every odd number n satisfy for that [1]
If n is a Fermat pseudoprime to base a, then n is a Fermat pseudoprime to base for every integer
Properties
Most of the Pseudoprimes, like Euler pseudoprime, Carmichael number, Fibonacci pseudoprime and Lucas pseudoprime, are Fermat pseudoprimes.
References and notes
- ↑ Richard E. Crandall and Carl Pomerance: Prime Numbers. A Computational Perspective. Springer Verlag , page 132, Therem 3.4.2.
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