Fermat pseudoprime: Difference between revisions
No edit summary |
|||
| Line 9: | Line 9: | ||
In other words, <math>n</math> divides <math>a^{n-1} - 1</math>, or, the order of <math>a</math> mod <math>n</math> divides <math>n - 1</math>. | In other words, <math>n</math> divides <math>a^{n-1} - 1</math>, or, the order of <math>a</math> mod <math>n</math> divides <math>n - 1</math>. | ||
==Facts== | |||
* [[Formula for number of bases to which a number is a Fermat pseudoprime]] | |||
==Relation with other properties== | ==Relation with other properties== | ||
Latest revision as of 21:36, 3 January 2012
Template:Base-relative pseudoprimality property This is not to be confused with Fermat prime
Definition
Suppose is a composite natural number and is relatively prime to . is termed a Fermat pseudoprime relative to base if we have:
.
In other words, divides , or, the order of mod divides .
Facts
Relation with other properties
Stronger properties
- Strong pseudoprime to a given base.
- Euler pseudoprime to a given base.
- Euler-Jacobi pseudoprime to a given base.
Property when applied to one or more choice of base
- Carmichael number is a number that is a Fermat pseudoprime for every (relatively prime) base.
- Poulet number is a Fermat pseudoprime to base (in particular, it needs to be an odd number).
