---
tag: 02M2K4QH9P
kind: definition
name: Fermat pseudoprime
msc: [11A51]
defines: 0W93FJAC8F
uses: [0N3ADXHNTQ, 0TPW25CBN6, 0M25PRN3WQ]
sources:
  - url: https://en.wikipedia.org/wiki/Fermat_pseudoprime
    locator: Definition
---

## Definition

Let $a$ be an integer with $a > 1$.
A Fermat pseudoprime to the base $a$ is a [[composite number|0N3ADXHNTQ]] $n$ such that $a^{n-1} \equiv 1 \pmod n$.

## Remarks

[[Fermat's little theorem|0M25PRN3WQ]] says that each prime $n$ with $n \nmid a$ satisfies $a^{n-1} \equiv 1 \pmod n$. A Fermat pseudoprime is a composite number that passes the same test.
The smallest Fermat pseudoprime to the base $2$ is $341 = 11 \cdot 31$.
The condition implies $\gcd(a, n) = 1$.
A composite number that is a Fermat pseudoprime to each base coprime to it is a [[Carmichael number|0TA7WT68RK]].

## Explanations

### L1 human

The [[Fermat primality test|0N5ZSZMYH6]] declares $n$ "probably prime" when $a^{n-1} \equiv 1 \pmod n$.
A Fermat pseudoprime is a composite number that fools this test for the base $a$.
For example, $2^{340} \equiv 1 \pmod{341}$, but $341$ is not prime.