Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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

1 Answer 1

up vote 5 down vote accepted

"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.

share|improve this answer
2  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.