Merseinne Primes

  • Thread starter Canute
  • Start date
  • #1
1,559
0
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?
 

Answers and Replies

  • #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
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?
 
  • #4
matt grime
Science Advisor
Homework Helper
9,420
4
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.
 
  • #5
1,559
0
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.
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?
 
  • #6
matt grime
Science Advisor
Homework Helper
9,420
4
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.
 
  • #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
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
 
  • #9
1,056
0

Related Threads on Merseinne Primes

  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
17
Views
3K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
4
Views
3K
  • Last Post
2
Replies
27
Views
5K
  • Last Post
Replies
6
Views
5K
  • Last Post
Replies
8
Views
6K
  • Last Post
Replies
3
Views
3K
Top