# Definition:Fermat Pseudoprime

## Definition

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

Then $q$ is a **Fermat pseudoprime to base $n$**.

### Fermat Pseudoprimes to base $2$ (Poulet Numbers)

Fermat pseudoprimes to base $2$ are known as Poulet numbers:

Let $q$ be a composite number such that $2^q \equiv 2 \pmod q$.

Then $q$ is a **Poulet number**.

### Fermat Pseudoprimes to base $3$

Let $q$ be a composite number such that $3^q \equiv 3 \pmod q$.

Then $q$ is a **Fermat pseudoprime to base $3$**.

### Fermat Pseudoprimes to base $4$

Let $q$ be a composite number such that $4^q \equiv 4 \pmod q$.

Then $q$ is a **Fermat pseudoprime to base $4$**.

### Fermat Pseudoprimes to base $5$

Let $q$ be a composite number such that $5^q \equiv 5 \pmod q$.

Then $q$ is a **Fermat pseudoprime to base $5$**.

## Also known as

It is common practice to refer to a **Fermat pseudoprime** just as a **pseudoprime**.

However, there is a concept in order theory also called a **pseudoprime**.

Hence the full name **Fermat pseudoprime** is preferred on $\mathsf{Pr} \infty \mathsf{fWiki}$.

Some sources hyphenate the word **pseudo-prime**.

A **Fermat pseudoprime** is also known as a **Fermat liar**.

## Also see

- Fermat's Little Theorem: 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.

Such counterexamples are not easy to find.

- Definition:Carmichael Number: an even rarer composite number $q$ such that $\forall n \in \N, n \perp q: n^q \equiv n \pmod q$.

## Source of Name

This entry was named for Pierre de Fermat.

## Historical Note

From as far back as the ancient Chinese, right up until the time of Gottfried Wilhelm von Leibniz, 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.

But it was discovered that $2^{341} \equiv 2 \pmod {341}$, and $341 = 31 \times 11$ and so is composite.

## Sources

- 1986: David Wells:
*Curious and Interesting Numbers*... (previous) ... (next): $91$ - 1997: David Wells:
*Curious and Interesting Numbers*(2nd ed.) ... (previous) ... (next): $91$ - 2014: Christopher Clapham and James Nicholson:
*The Concise Oxford Dictionary of Mathematics*(5th ed.) ... (previous) ... (next):**pseudo-prime**

- Weisstein, Eric W. "Fermat Pseudoprime." From
*MathWorld*--A Wolfram Web Resource. https://mathworld.wolfram.com/FermatPseudoprime.html