Mersenne number for prime or Poulet implies prime or Poulet

Statement

Suppose $n$ is a natural number such that:

$2^{n-1}\equiv 1{\pmod {n}}$.

Consider the $n^{th}$ Mersenne number $M_{n}=2^{n}-1$. Then, we have:

$2^{M_{n}-1}\equiv 1{\pmod {M_{n}}}$.

In other words, the Mersenne number for a number that is either a prime number or a Poulet number (i.e., an odd composite number that is pseudoprime to base $2$), is also either a prime number or a Poulet number.

Related facts

Applications

• Infinitude of Poulet numbers

Proof

Given: A natural number $n$ such that $2^{n-1}\equiv 1{\pmod {n}}$.

To prove: $2^{M_{n}-1}\equiv 1{\pmod {M_{n}}}$.

Proof: By assumption, $n$ divides $2^{n-1}-1$, so there exists an integer $k$ such that $kn=2^{n-1}-1$. Thus, $M_{n}-1=2^{n}-2=2(2^{n-1}-1)=2kn$. Thus, we have:

$2^{M_{n}-1}=2^{2kn}=(2^{2kn}-1)+1$.

Since $M_{n}=2^{n}-1$ divides $2^{2kn}-1$, we get that:

$2^{M_{n}-1}\equiv 1{\pmod {M_{n}}}$.