Fermat pseudoprime

Template:Base-relative pseudoprimality property This is not to be confused with Fermat prime

Definition

Suppose $n$ is a composite natural number and $a$ is relatively prime to $n$. $n$ is termed a Fermat pseudoprime relative to base $a$ if we have:

$a^{n-1}\equiv 1modn$.

In other words, $n$ divides $a^{n-1}-1$, or, the order of $a$ mod $n$ divides $n-1$.

Facts

• Formula for number of bases to which a number is a Fermat pseudoprime

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 $2$ (in particular, it needs to be an odd number).