Fermat pseudoprime

In number theory, the Fermat pseudoprimes make up the most important class of pseudoprimes that come from Fermat's little theorem.

Definition

Fermat's little theorem states that if

p

{\displaystyle p}

is prime and

a

{\displaystyle a}

is coprime to

p

{\displaystyle p}

, then

a

p

−

1

−

1

{\displaystyle a^{p-1}-1}

is divisible by

p

{\displaystyle p}

. For a positive integer

a

{\displaystyle a}

, if a composite integer

x

{\displaystyle x}

divides

a

x

−

1

−

1

{\displaystyle a^{x-1}-1}

then

x

{\displaystyle x}

is called a Fermat pseudoprime to base

a

{\displaystyle a}

.

In other words, a composite integer is a Fermat pseudoprime to base

a

{\displaystyle a}

if it successfully passes the Fermat primality test for the base

a

{\displaystyle a}

. The false statement that all numbers that pass the Fermat primality test for base 2 are prime is called the Chinese hypothesis.

The smallest base-2 Fermat pseudoprime is 341. It is not a prime, since it equals 11·31, but it satisfies Fermat's little theorem:

2

340

≡

1

(

mod

341

)

{\displaystyle 2^{340}\equiv 1({\bmod {341}})}

and thus passes the

Fermat primality test for the base 2.

Pseudoprimes to base 2 are sometimes called Sarrus numbers, after P. F. Sarrus who discovered that 341 has this property, Poulet numbers, after P. Poulet who made a table of such numbers, or Fermatians (sequence A001567 in the OEIS).

A Fermat pseudoprime is often called a pseudoprime, with the modifier Fermat being understood.

An integer

x

{\displaystyle x}

that is a Fermat pseudoprime for all values of

a

{\displaystyle a}

that are coprime to

x

{\displaystyle x}

is called a Carmichael number.