Merseinne Primes: Question from a Maths Dunce

[Canute]

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?

 

[matt grime]

x must be prime, so they only use prime exponents anyway.

 

[Canute]

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?

 

[matt grime]

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.

 

[Canute]

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.

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?

 

[matt grime]

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.

 

[Canute]

Yes, sorry, that's what I meant. I get it now. Thanks. I was looking at it back to front.

 

[T.Rex]

The GIMPS

You can find more information on the GIMPS web-side:
http://www.mersenne.org/prime.htm
and on their forum:
http://www.mersenneforum.org/index.php?

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 .

Tony

 

[robert Ihnot]

Note: If N==3 Mod 4 and 2N+1 is prime (Called a Sophia Germain prime), then:

(2^n)-1 is divisible by 2n+1. Thus 2^11 -1 = 23*89, 2^23 -1 =47*178481.

See:http://nrich.maths.org/askedNRICH/edited/2186.html