Definition:Poulet Number

From ProofWiki
Jump to navigation Jump to search


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

Then $q$ is a Poulet number.

Sequence of Poulet Numbers

The sequence of Poulet numbers begins:

$341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, \ldots$

Examples of Poulet Numbers

$341$ is a Poulet Number

The smallest Poulet number is $341$:

$2^{341} \equiv 2 \pmod {341}$

despite the fact that $341$ is not prime:

$341 = 11 \times 31$

Also known as

Poulet numbers are also referred to as pseudoprimes or Fermat pseudoprimes to base $2$.

Some sources refer to them as Sarrus numbers, for Pierre Frédéric Sarrus.

Source of Name

This entry was named for Paul Poulet.

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.

The first person to point this out was Pierre Frédéric Sarrus, in whose honour these numbers are sometimes called Sarrus numbers.

Paul Poulet set about calculating these Fermat pseudoprimes to base $2$, first up to $50$ million in $1926$, then up to $100$ million in $1938$.

They have since been named Poulet numbers in honour of that feat of calculation.

It has been determined by John Lewis Selfridge and Samuel Standfield Wagstaff Jr. that in the first $20 \, 000 \, 000 \, 000$ positive integers there are no more than $19 \, 865$ Poulet numbers.