Mersenne Prime Calculator: Testing 2ᵖ − 1 and the Link to Perfect Numbers
About the Author
Marko Šinko
Co-Founder & Lead Developer, AI Math Calculator
A Mersenne prime calculator handles a shape of number that ordinary primality tools give up on. Feed a general-purpose prime checker a 13,395-digit integer and it will still be thinking about it next week. Feed the same number to the Lucas–Lehmer test and you get a definitive yes or no, because 2p − 1 has so much structure that a test exists which works on nothing else. That single fact is why the largest known prime has been a Mersenne prime for all but a handful of years since 1876.
The tool above builds 2p − 1 from the exponent you type, then decides it by whichever route is cheapest: a composite exponent, an explicit factor pulled from the 2kp + 1 progression, or the full Lucas–Lehmer run with the residues on screen. What follows is why the exponent has to be prime, why that is nowhere near enough, how the test actually works on paper, and the theorem that ties every one of these numbers to a perfect number.
Powers of Two, Minus One
A Mersenne number is any integer of the form Mp = 2p − 1. In binary it is a string of p ones and nothing else: M4 = 1111₂ = 15, M7 = 1111111₂ = 127. When such a number happens to be prime, it is a Mersenne prime.
The name comes from Marin Mersenne, a French monk who in 1644 published a list of the exponents below 257 he believed produced primes. He got five of them wrong — he included 67 and 257, which are composite, and missed 61, 89 and 107. It took nearly three centuries to sort out, which tells you something about how hard these are to check by hand.
Start with the first rule, because it eliminates most candidates before any real work begins. If p is composite, Mp is composite. The reason is a factorisation you can write down in one line. If p = ab, then
Try it on p = 6 = 2 × 3: 26 − 1 = 63, and the formula predicts (2² − 1)(2⁴ + 2² + 1) = 3 × 21 = 63. Correct, and the factor 3 came out without a single trial division. The calculator applies this check first, which is why entering p = 100 returns an answer instantly instead of grinding through a 31-digit number.
Why 2047 Ruins the Obvious Guess
Here is where almost everyone slips. The exponent rule runs one way only: p must be prime for Mp to be prime, but a prime p guarantees nothing. The smallest counterexample is small enough to be embarrassing.
Below 100 the hit rate is already poor. Of the 25 primes under 100, only 2, 3, 5, 7, 13, 17, 19, 31, 61 and 89 produce Mersenne primes — ten out of twenty-five, and the rate collapses from there. Among all 5,761,455 primes below 100 million, exactly 52 are known to work.
What saves the search from hopelessness is a second structural result, due to Euler: every divisor q of Mp with p prime satisfies q ≡ 1 (mod 2p) and q ≡ ±1 (mod 8). Instead of testing every integer up to √Mp, you walk one thin arithmetic progression. For p = 11 that means testing 23, 89, 199, … and 23 divides 2047 on the first candidate. For p = 29 the smallest factor is 233; for p = 59 it is 179,951. This is exactly what the calculator does before it reaches for anything heavier, and it disposes of a large share of exponents in milliseconds.
The most famous demonstration of the difficulty is Frank Nelson Cole’s 1903 lecture to the American Mathematical Society. He walked to the board, said nothing, computed 267 − 1, then multiplied 193,707,721 by 761,838,257,287 and got the same number. He sat down to a standing ovation without having spoken a word. Asked later how long it took him, he said “three years of Sundays.” Enter p = 67 above and you will get the same verdict in well under a second — though the factor itself is above the fast search window, so the answer comes from Lucas–Lehmer instead.
The Lucas–Lehmer Test, Worked Through by Hand
For a prime exponent p > 2, define a sequence and read off one value at the end:
Mp is prime ⟺ sp−2 = 0
That is the whole test. No factors, no guessing, no probability — it is deterministic, and it needs exactly p − 2 squarings. Take p = 7, so M₇ = 127 and we run five steps:
| Step | sᵢ² − 2 | mod 127 |
|---|---|---|
| s₀ | start | 4 |
| s₁ | 4² − 2 = 14 | 14 |
| s₂ | 14² − 2 = 194 | 67 |
| s₃ | 67² − 2 = 4487 | 42 |
| s₄ | 42² − 2 = 1762 | 111 |
| s₅ | 111² − 2 = 12319 | 0 |
s₅ = sp−2 = 0, so 127 is prime. Now run the same machinery on p = 11, where M₁₁ = 2047 and nine steps are needed: 4 → 14 → 194 → 788 → 701 → 119 → 1877 → 240 → 282 → 1736. The last residue is 1,736 rather than 0, so 2047 is composite — and notice the test says so without ever revealing that the factors are 23 and 89. Lucas–Lehmer answers “is it prime” and nothing more, which is precisely why factoring these numbers remains hard even when their status is known.
What a Mersenne Prime Calculator Does Instead of Trial Division
The cost is what makes the whole enterprise possible. Trial division on a 41-million-digit number is not slow, it is impossible — there is no machine and no timescale that would finish it. Lucas–Lehmer needs p − 2 modular squarings, and with a fast Fourier transform each squaring costs roughly O(p log p). That turns an unreachable problem into a few days of GPU time.
There is one more saving specific to this family. Reducing mod 2p − 1 normally means a full division, but because 2p ≡ 1 for this modulus, the reduction is just “shift the high bits down and add them to the low bits.” No division ever runs. That is the trick the calculator above uses, and it is why an exponent in the low thousands resolves inside a single keystroke. Here is how the four realistic approaches compare:
| Method | Works on | Cost for p = 82,589,933 | Answer type |
|---|---|---|---|
| Trial division | any integer | ~1012,000,000 divisions | certain, plus a factor |
| 2kp + 1 sieve | Mersenne, prime p | seconds — but usually finds nothing | composite, plus a factor |
| Miller–Rabin | any integer | days per round | probable prime only |
| Lucas–Lehmer | Mersenne only | days on one GPU | certain, no factor |
Every Even Perfect Number Hides a Mersenne Prime
A perfect number equals the sum of its proper divisors: 6 = 1 + 2 + 3, and 28 = 1 + 2 + 4 + 7 + 14. Euclid proved around 300 BC that if 2p − 1 is prime, then
is perfect. Two thousand years later Euler proved the converse: every even perfect number has that form. Together they are the Euclid–Euler theorem, and the practical consequence is a one-to-one correspondence — 52 known Mersenne primes, 52 known even perfect numbers, no others possible.
| p | 2ᵖ − 1 | 2ᵖ⁻¹(2ᵖ − 1) | Divisor check |
|---|---|---|---|
| 2 | 3 | 6 | 1+2+3 |
| 3 | 7 | 28 | 1+2+4+7+14 |
| 5 | 31 | 496 | 1+2+4+…+248 |
| 7 | 127 | 8,128 | 1+2+4+…+4064 |
| 13 | 8,191 | 33,550,336 | 28 divisors |
Notice the gap between the fourth and fifth rows: 8,128 was known to the Greeks, and the next one is 33.5 million. There is nothing in between, which is why the ancient world stopped at four. If you want to see the divisor sums verified rather than asserted, the perfect number calculator expands them, and the prime factorization calculator shows why 2p−1Mp has exactly 2p divisors when Mp is prime.
The open question is odd perfect numbers. Nobody has found one and nobody has proved none exist, but the constraints are brutal: any odd perfect number must exceed 101500, have at least 101 prime factors counted with multiplicity, and at least 10 distinct ones. Most number theorists expect the answer is that they do not exist.
From 39 Digits to 41 Million in 150 Years
Édouard Lucas verified M₁₂₇ = 170141183460469231731687303715884105727 by hand in 1876 — 39 digits, using an early form of the test that bears his name. It held the record for seventy-six years, the longest reign of any largest-known prime, and it is still the largest prime ever verified without a computer.
Then in 1952 Raphael Robinson ran the SWAC machine and found five new ones in a single year. Since 1996 every discovery has come from GIMPS, the Great Internet Mersenne Prime Search, which distributes candidate exponents to volunteers’ idle CPUs and GPUs. The current record, M₅₂ with p = 136,279,841, was found in October 2024 by Luke Durant using a cloud GPU network — 41,024,320 digits, which would fill roughly 13,000 printed pages.
A caveat on the numbering that trips people up: an entry is only confirmed to be the nth Mersenne prime once every exponent below it has been tested at least once. That sweep is finished for the lower entries, but the highest few are numbered by discovery order. There may still be an unfound Mersenne prime sitting in an untested gap, which would shift the labels. The All 52 known tab lists every entry with its exponent, digit count, year and discoverer.
Four Ways Mersenne Calculations Go Wrong
Entering the Mersenne number instead of the exponent. The field wants p, not 2p − 1. Typing 127 tests M₁₂₇, a 39-digit number, not the prime 127 itself. Both happen to be Mersenne primes, which makes this mistake unusually easy to miss.
Assuming a prime exponent is enough. Covered above, but it bears repeating because it is the single most common error on exams: p prime is necessary, not sufficient. If you need to check the exponent itself first, the prime calculator settles that in one step.
Starting Lucas–Lehmer at the wrong seed or step count. s₀ = 4, and you stop at sp−2, not sp or sp−1. For p = 7 that is five squarings. Run one step too many and s₅ = 0 becomes s₆ = −2 mod 127 = 125, and a genuine prime reads as composite.
Reducing mod Mp only at the end. The intermediate values double in length every step. Skip the reduction and by step 10 you are holding a 617-digit number, by step 20 a 631,296-digit one, and by step 125 — the last step for p = 127 — a number with roughly 1037 digits, which no amount of memory can hold. Reduce after every squaring, not at the end.
One last practical note. Mersenne primes are not merely a curiosity: they are the modulus behind the Mersenne Twister random number generator (period 219937 − 1, from M₂₄ on the list), and 231 − 1 = 2,147,483,647 — Euler’s prime — is the reason signed 32-bit integers stop where they do. You have almost certainly used one today without noticing. For background beyond the calculator, Wikipedia’s Mersenne prime entry keeps a maintained record of the search.
