Mersenne Primes

What just happened?

Mersenne numbers are numbers of the form $M_p = 2^p - 1$. For some exponents $p$ this number is prime — we then call it a Mersenne prime:

Examples: $2^2-1=3$, $2^3-1=7$, $2^5-1=31$, $2^7-1=127$ — all prime. But $2^{11}-1 = 2047 = 23\cdot 89$ is already composite, even though 11 is prime.

The key property (the invariant):

For $2^p-1$ to be prime, the exponent $p$ itself must be prime:

The implication works only one way. If $p = a\cdot b$ were composite, then $2^a-1$ would divide $2^p-1$ — so the number would not be prime. The converse need not hold, however: not every prime $p$ gives a Mersenne prime (counterexample: $p=11$).

Where does the name come from, and why does it matter?

These numbers bear the name of the French monk and scholar Marin Mersenne, who in 1644 (“Cogitata Physico-Mathematica”) gave a list of exponents $p$ giving — as he believed — primes. His list contained a few errors, corrected only in the 20th century. Mersenne primes are closely tied to perfect numbers (the Euclid–Euler formula).

Why do the records belong to Mersenne?

For numbers of this form there is an exceptionally fast primality test — the Lucas–Lehmer test — working only for $2^p-1$. That is why the record-breaking large known primes are almost always Mersenne numbers. The GIMPS project (Great Internet Mersenne Prime Search, since 1996) uses the computing power of thousands of volunteers’ computers worldwide; the largest known prime (2024) has over 41 million digits.

Why this matters for your exam:

This is a model example that a necessary condition need not be sufficient: “$p$ prime” is necessary for $2^p-1$ to be prime, but does not guarantee primality. Telling an implication from an equivalence is a classic exam topic — and the primes are the foundation of modern cryptography.

Remember: $M_p = 2^p-1$; if $2^p-1$ is prime, then $p$ is too — but not the other way round. The largest known primes are Mersenne numbers, found today by the GIMPS project.