Mersenne Prime Finder
Solve mersenne prime problems step-by-step with our free calculator. See formulas, worked examples, and clear explanations.
Reviewed for accuracy by Manoj Kumar, Mathematics Educator
Mersenne Prime Finder
Calculator
Adjust values & calculateEnter your values below. Every result is computed in your browser — no data is sent to any server.
Formula: M(p) = 2^p - 1
Worked example — M17 = 131,071 is a Mersenne prime | Perfect number: 8,589,869,056
Formula
M(p) = 2^p - 1
A Mersenne number M(p) equals 2 raised to the power p minus 1. When both p is prime and M(p) is prime, M(p) is called a Mersenne prime. The associated even perfect number is 2^(p-1) * M(p).
Worked Examples
Example 1: Verifying M17 = 2^17 - 1 is Prime
Problem:Check whether 2^17 - 1 = 131,071 is a Mersenne prime.
Solution:First confirm 17 is prime: not divisible by 2, 3, or any prime up to sqrt(17) = 4.12. 2^17 - 1 = 131,071 Check divisibility by primes up to sqrt(131071) = 362. No prime factor found, confirming 131,071 is prime. Associated perfect number: 2^16 * 131,071 = 8,589,869,056
Result:M17 = 131,071 is a Mersenne prime | Perfect number: 8,589,869,056
Example 2: Showing M11 = 2^11 - 1 is NOT Prime
Problem:Test whether 2^11 - 1 = 2,047 is a Mersenne prime despite 11 being prime.
Solution:2^11 - 1 = 2,047 Check divisibility: 2047 / 23 = 89 So 2047 = 23 * 89, which is composite. Note: The factor 23 = 2 * 11 + 1, illustrating that factors of Mersenne numbers 2^p - 1 must be of the form 2kp + 1.
Result:M11 = 2,047 = 23 * 89 is NOT a Mersenne prime
Frequently Asked Questions
What is a Mersenne prime and why are they important?
A Mersenne prime is a prime number that can be written in the form 2^p - 1, where p itself must also be a prime number. They are named after the French monk Marin Mersenne, who studied them in the 17th century. Mersenne primes are important because they are deeply connected to perfect numbers through the Euclid-Euler theorem, and they hold records as the largest known prime numbers. The Great Internet Mersenne Prime Search (GIMPS) project has discovered the largest known primes, all of which are Mersenne primes. As of recent records, the largest known prime has over 41 million digits and is a Mersenne prime.
Why must the exponent p be prime for 2^p - 1 to be prime?
If the exponent p is composite, meaning p = a * b where both a and b are greater than 1, then 2^p - 1 can always be factored algebraically. Specifically, 2^(ab) - 1 is divisible by 2^a - 1 and also by 2^b - 1. For example, 2^6 - 1 = 63 = 9 * 7, and indeed 2^2 - 1 = 3 divides 63 and 2^3 - 1 = 7 divides 63. This algebraic factorization means composite exponents can never yield primes. However, having a prime exponent is necessary but not sufficient, since 2^11 - 1 = 2047 = 23 * 89 is composite despite 11 being prime.
How does the Lucas-Lehmer primality test work?
The Lucas-Lehmer test is the most efficient known method for determining whether a Mersenne number 2^p - 1 is prime for an odd prime p. The test works by computing a sequence: start with s(0) = 4, then repeatedly compute s(i) = s(i-1)^2 - 2, taking each result modulo 2^p - 1. After p - 2 iterations, if s(p-2) is congruent to zero modulo 2^p - 1, then 2^p - 1 is prime. This test is remarkably efficient because arithmetic modulo 2^p - 1 can be done very quickly using bitwise operations. It is the primary algorithm used by the GIMPS distributed computing project to search for new Mersenne primes.
What is the connection between Mersenne primes and perfect numbers?
The Euclid-Euler theorem establishes a one-to-one correspondence between Mersenne primes and even perfect numbers. If 2^p - 1 is a Mersenne prime, then 2^(p-1) * (2^p - 1) is an even perfect number. Conversely, every even perfect number has this form. For example, the Mersenne prime 2^2 - 1 = 3 gives the perfect number 2^1 * 3 = 6, and the Mersenne prime 2^3 - 1 = 7 gives the perfect number 2^2 * 7 = 28. Whether odd perfect numbers exist remains one of the oldest unsolved problems in mathematics. This beautiful connection means that discovering each new Mersenne prime automatically gives a new perfect number.
How many Mersenne primes are currently known?
As of early 2025, there are 51 known Mersenne primes. The search for new ones is ongoing through the Great Internet Mersenne Prime Search (GIMPS), a collaborative distributed computing project that anyone can join. The first few Mersenne primes correspond to exponents 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, and 127. The exponents grow increasingly sparse and unpredictable. It is an open question whether there are infinitely many Mersenne primes, though most mathematicians believe there are. Each new discovery requires testing enormous numbers and typically takes months of continuous computation across thousands of volunteer computers worldwide.
What is GIMPS and how can I participate in the search?
GIMPS, the Great Internet Mersenne Prime Search, is a distributed computing project founded by George Woltman in 1996 that harnesses the idle processing power of volunteers' computers to search for new Mersenne primes. To participate, you download the free Prime95 software (or MPrime for Linux), which runs primality tests on assigned exponents when your computer is idle. GIMPS has discovered 17 Mersenne primes and won the Electronic Frontier Foundation prizes for finding primes with over 1 million and 10 million digits. The project assigns each volunteer a range of untested exponents and coordinates results to ensure no gaps in the search. The current search frontier is around exponents near 100 million.
What is the difference between Mersenne numbers and Mersenne primes?
A Mersenne number is any number of the form 2^n - 1 for a positive integer n. A Mersenne prime is a Mersenne number that happens to be prime. Most Mersenne numbers are composite. For example, 2^4 - 1 = 15 = 3 * 5 is a Mersenne number but not a Mersenne prime. Only when the exponent n is itself prime does 2^n - 1 have a chance of being prime, and even then most are composite. Out of all prime exponents tested up to several hundred million, only 51 yield Mersenne primes. The density of Mersenne primes among Mersenne numbers with prime exponents decreases as the exponents grow larger, following conjectured heuristic distributions.
Can Mersenne primes be used in cryptography?
Mersenne primes have specialized applications in cryptography and pseudorandom number generation. The Mersenne Twister, one of the most widely used pseudorandom number generators, is based on properties of Mersenne primes (specifically 2^19937 - 1). In RSA cryptography, while Mersenne primes themselves are not used directly as key components because their special form would make them easy to guess, the mathematical theory behind primality testing of Mersenne numbers has advanced general prime-testing algorithms. Additionally, the binary structure of Mersenne numbers (all 1s in binary representation) makes modular arithmetic with them extremely efficient, which benefits various cryptographic implementations.
What patterns exist among Mersenne prime exponents?
Despite extensive research, no reliable pattern or formula predicts which prime exponents yield Mersenne primes. The known exponents are 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, and so on, with gaps that grow increasingly irregular. The Lenstra-Pomerance-Wagstaff conjecture suggests that the number of Mersenne primes with exponent less than N is approximately e^gamma * log2(N) / log(N), where gamma is the Euler-Mascheroni constant. This predicts roughly 5.92 Mersenne primes per ten-fold increase in exponent size. There are also curious observations, like the clustering of exponents near powers of 2, but none of these patterns have been proven to hold in general.
How are Mersenne numbers related to binary representations?
Mersenne numbers have a beautifully simple binary representation: 2^p - 1 in binary is simply p consecutive ones. For example, 2^5 - 1 = 31 in binary is 11111, and 2^7 - 1 = 127 is 1111111. This all-ones binary pattern is why Mersenne numbers are sometimes called binary repunits. This structure makes modular reduction very efficient in hardware and software, requiring only bit shifts and additions instead of expensive division operations. This efficiency is exploited in computer architecture, hash functions, and the Lucas-Lehmer primality test. The connection to binary also means that perfect numbers (derived from Mersenne primes) have elegant binary representations as well.
References
Reviewed for accuracy by Manoj Kumar, Mathematics Educator · Editorial policy
Related Calculators
🧮Polynomial Root Finder
Calculate polynomial root finder with inputs, formulas, and instant results.
🧮Prime Factorization Calculator
Calculate prime factorization with inputs, formulas, and instant results.
🧮Prime Number Calculator
Calculate prime number with inputs, formulas, and instant results.
🧮Relatively Prime Calculator
Calculate relatively prime with inputs, formulas, and instant results.
🧮Prime Counting Function Calculator
Calculate prime counting function with inputs, formulas, and instant results.
🧮Greatest Common Factor Calculator
Find the GCF (GCD) of two or more numbers using prime factorization and Euclidean algorithm.
🧮Least Common Multiple Calculator
Find the LCM of two or more numbers using prime factorization and the GCF method.
🧮Miller-Rabin Primality Test Calculator
Test if large numbers are prime using the Miller-Rabin probabilistic primality test.