- #1

- 1,559

- 0

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?

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter Canute
- Start date

- #1

- 1,559

- 0

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

matt grime

Science Advisor

Homework Helper

- 9,420

- 4

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

- #3

- 1,559

- 0

- #4

matt grime

Science Advisor

Homework Helper

- 9,420

- 4

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.

- #5

- 1,559

- 0

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 said: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.

- #6

matt grime

Science Advisor

Homework Helper

- 9,420

- 4

- #7

- 1,559

- 0

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

- #8

- 62

- 0

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

- #9

- 1,056

- 0

(2^n)-1 is divisible by 2n+1. Thus 2^

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

Share: