# Why are Mersenne primes easier to find?

9 out of 10 biggest known prime numbers are Mersenne numbers. Are they easier to find?

rank    prime   digits  who when    reference
1   2**243112609-1  12978189    G10 2008    Mersenne 47??
2   2**242643801-1  12837064    G12 2009    Mersenne 46??
3   2**237156667-1  11185272    G11 2008    Mersenne 45?


http://primes.utm.edu/largest.html

-
The base-2 repunits are Mersenne numbers and computers use binary. –  glebovg Oct 21 '12 at 23:34

"Easier to find" is not quite the right thing to say. The question is this: you want to pick an extremely large number to test for primality. What kind of large numbers should you test? A "random" large number is a bad choice: such a number will have a probability of approximately $\frac{1}{2}$ of being even, a probability of approximately $\frac{1}{3}$ of being divisible by $3$, and so forth.

Mersenne numbers, on the other hand, are both extremely large and substantially more likely than "random" large numbers to be prime. Indeed, if $q$ divides a Mersenne number $2^p - 1$, then $q \equiv 1 \bmod p$ by Lagrange's theorem. This is a far smaller list of possible prime divisors, and in particular no prime less than or equal to $p$ can be a divisor.

There is also a specialized primality test, the Lucas-Lehmer test, which is specific to Mersenne numbers.

-
The last part is by far the most important. The Lucas-Lehmer test is about as fast as probable-prime testing, and tests for general forms are far slower. –  Charles Oct 22 '12 at 14:35
Any prime divisor of 2^p-1 must be of the form 2kp+1. Thus "in particular no prime less than 2p can be a divisor.". –  jnml Oct 30 '12 at 10:57