Definition:Fermat Pseudoprime

From ProofWiki
Jump to navigation Jump to search

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

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.



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

Retrieved from "https://proofwiki.org/w/index.php?title=Definition:Fermat_Pseudoprime&oldid=713537"