7
$\begingroup$

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

  • 0
    The base-2 repunits are Mersenne numbers and computers use binary.2012-10-21

1 Answers 1

8

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

  • 0
    Any prime divi$s$or of 2^p-1 mu$s$t be of the form 2kp+1. Thus "in parti$c$ular no prime less than 2p $c$an be a divi$s$or.".2012-10-30