Definition:Fermat Pseudoprime/Base 4

Definition

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

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

Sequence

The sequence of Fermat pseudoprimes base $4$ begins:

$15, 85, 91, 341, 435, 451, 561, 645, 703, 1105, 1247, 1271, 1387, 1581, 1695, 1729, 1891, 1905, 2047, 2071, 2465, \ldots$

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): $217$