# Definition:Fermat Pseudoprime/Base 3

< Definition:Fermat Pseudoprime(Redirected from Definition:Fermat Pseudoprime to Base 3)

Jump to navigation
Jump to search
## Contents

## Definition

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

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

### Sequence

The sequence of Fermat pseudoprimes base $3$ begins:

- $91, 121, 286, 671, 703, \ldots$

## Examples

### $91$ is a Fermat Pseudoprime to Base $3$

The smallest Fermat pseudoprime to base $3$ is $91$:

- $3^{91} \equiv 3 \pmod {91}$

despite the fact that $91$ is not prime:

- $91 = 7 \times 13$

## 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$