Mersenne Primes

By SkytrailGroup Mathematics Editorial Team April 12, 2026

Definition

Mₚ=2ᵖ−1 is prime only if p is prime (necessary, not sufficient). Known Mersenne primes: M₂=3, M₃=7, M₅=31, M₇=127, …

Examples

Example 1. Is M₅=31 prime?

Solution. 31 is prime. Yes.

In Depth

A Mersenne prime has the form \(M_p=2^p-1\) where \(p\) itself is prime (a necessary but not sufficient condition). The first few are \(M_2=3\), \(M_3=7\), \(M_5=31\), \(M_7=127\). Not all prime \(p\) give prime \(M_p\): \(M_{11}=2047=23\times89\).

The Lucas–Lehmer test efficiently checks whether \(M_p\) is prime: define \(s_0=4\), \(s_{k+1}=s_k^2-2\pmod{M_p}\); then \(M_p\) is prime iff \(s_{p-2}\equiv0\pmod{M_p}\). This deterministic test runs in \(O(p^3)\) bit operations and is the basis of GIMPS.

Every even perfect number corresponds to a Mersenne prime via Euclid's formula \(2^{p-1}(2^p-1)\). So the search for Mersenne primes is equivalent to the search for even perfect numbers. As of 2024, 51 Mersenne primes are known.

Mersenne primes are rare: heuristically, the probability that \(2^p-1\) is prime is approximately \(e^\gamma\ln 2/p\approx1.13/p\) (Wagstaff's conjecture), so the expected number of Mersenne primes with exponent up to \(N\) grows like \(e^\gamma\ln 2\cdot\ln N\).

Mersenne numbers \(M_p\) have special structure that makes them useful in computing: fast modular reduction modulo \(M_p\) uses only shifts and additions. This is exploited in cryptographic implementations and in the Fast Fourier Transform over finite fields.

Key Properties & Applications

The Lucas–Lehmer test is highly efficient: it requires only \(p-2\) squarings modulo \(M_p\), each taking \(O(p^2)\) bit operations naively or \(O(p\log p\log\log p)\) with FFT-based multiplication. This makes testing 100-million-digit Mersenne numbers feasible.

Mersenne numbers \(M_p=2^p-1\) have a special factorization structure: any prime factor \(q\) of \(M_p\) satisfies \(q\equiv1\pmod{p}\) and \(q\equiv\pm1\pmod{8}\). This restricts the possible factors and speeds up trial division.

The New Mersenne conjecture (Bateman, Selfridge, Wagstaff): if two of the three conditions hold — (1) \(p=2^k\pm1\) or \(p=4^k\pm3\), (2) \(2^p-1\) is prime, (3) \((2^p+1)/3\) is prime — then the third also holds. This is verified for all known cases but unproved.