Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Merseinne Primes

  1. Jan 19, 2005 #1
    Question from a mathematics dunce.

    I recently read that Merseinne primes are searched for using 2^x -1 where x is a number. Is this correct?

    If so why not use 6n+/-1 instead?
  2. jcsd
  3. Jan 19, 2005 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    x must be prime, so they only use prime exponents anyway.
  4. Jan 19, 2005 #3
    Does this mean that 11 is not a M prime? Why is 2^x -1 better than 6n+/-1. Does it in some way filter out more non-primes along with the primes it filters out?
  5. Jan 19, 2005 #4

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    A mersenne prime is one of the form 2^n - 1, it is easy to show that n is prime, if 2^n - 1 is. So they only look at prime exponents.

    11 a mersenne prime? Of course not, is 12 an integer power of 2?

    Not every number of the form 6n+/-1 is prime (eg 25) so they don't use 6n+/-1, however, all primes, except 2, 3 and 5 are of the form 6n+/-1.

    I'm a little confused as to what the problem is here.
  6. Jan 19, 2005 #5
    Ah. Maybe I'm looking at it back to front. I thought something was a bit odd about it. So, this a test of whether n is prime while avoiding factorising. Is that it?
  7. Jan 19, 2005 #6

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    No, they are testing whether 2^n - 1 is prime, but they can prove this can only happen if n is prime, so there's no need to check 2^n - 1 if n is composite. since 2^n - 1 is significantly larger than n, so it makes no sense to try and factorize it instead of n.
  8. Jan 19, 2005 #7
    Yes, sorry, that's what I meant. I get it now. Thanks. I was looking at it back to front.
  9. Feb 5, 2005 #8
    The GIMPS

    You can find more information on the GIMPS web-side:
    and on their forum:

    The GIMPS searchs for Mersenne primes because they are rare (but not as rare as Fermat primes) and because there is a very simple test for proving that they are prime or not (but the proof of the test is quite complex and computing the test for large q like ~26000000 takes a very long time).
    The test is:
    Let S_0=4 and S_{i+1}=S_i^2 - 2
    M_q is prime <==> S_{q-2} = k * M_q

    For q=3 , M_q = 2^3-1=7 S_1=14=2*7 : M_3 is prime.
    For q=5 , M_q = 2^5-1=31 S_1=14 S_2=194 S_3=37634=2*31*607 : M_5 is prime .

    The first Mersenne composite number (with q prime) is M_11 .

  10. Feb 6, 2005 #9
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook