Definition:Fermat Pseudoprime

Definition

Fermat's Little Theorem tells us that if $p$ is a prime, then $\forall n \in \N: n^p \equiv n \pmod p$.

However, it is not always the case that if $\forall n \in \N: n^p \equiv n \pmod p$ then $p$ is prime.

Let $q$ be a composite number such that $\exists n \in N: n^q \equiv n \pmod q$.

Such numbers $q$ are called Fermat pseudoprimes or Fermat liars and they are not easy to find.

If $q$ is composite number such that $\forall n \in N: n^q \equiv n \pmod q$, then such a number is a Carmichael number, and those are even rarer.

Historical Note

For a long time it was thought that $n$ had to be prime in order for $2^n - 2$ to be divisible by $n$. This used to be used as a test for primality.

However, it was discovered that $2^{341} \equiv 2 \pmod {341}$.

However, $341 = 31 \times 11$ and so is composite.

Source of Name

This entry was named for Pierre de Fermat.