Merseinne Primes: Question from a Maths Dunce

  • Context: Undergrad 
  • Thread starter Thread starter Canute
  • Start date Start date
  • Tags Tags
    Primes
Click For Summary

Discussion Overview

The discussion centers around Mersenne primes, specifically the form 2^n - 1, and the conditions under which they are considered prime. Participants explore the rationale behind using prime exponents and compare this method to the alternative form of 6n±1.

Discussion Character

  • Exploratory
  • Technical explanation
  • Debate/contested

Main Points Raised

  • One participant questions whether Mersenne primes are correctly defined and suggests using the form 6n±1 instead.
  • Another participant clarifies that only prime exponents are used in the search for Mersenne primes.
  • A participant expresses confusion about the relationship between the primality of n and the primality of 2^n - 1, seeking clarification on the filtering process.
  • It is noted that not every number of the form 6n±1 is prime, which is why this form is not used in the search for Mersenne primes.
  • Participants discuss that the test for Mersenne primes effectively checks if 2^n - 1 is prime, under the condition that n must be prime.
  • One participant acknowledges a misunderstanding and realizes that the focus is on testing the primality of 2^n - 1 rather than n itself.
  • Information about the GIMPS project is shared, highlighting the rarity of Mersenne primes and the complexity of the tests used to verify their primality.
  • A note is made about the relationship between certain primes and divisibility conditions related to Mersenne primes.

Areas of Agreement / Disagreement

Participants express varying levels of understanding regarding the conditions for Mersenne primes and the rationale behind the methods used. There is no clear consensus on the superiority of one method over another, and some confusion remains about the implications of using different forms.

Contextual Notes

There are unresolved questions about the effectiveness of the 6n±1 form in relation to Mersenne primes and the implications of primality testing for composite numbers. The discussion reflects a mix of technical reasoning and exploratory questioning.

Canute
Messages
1,572
Reaction score
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?
 
Physics news on Phys.org
x must be prime, so they only use prime exponents anyway.
 
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?
 
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.
 
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?
 
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.
 
Yes, sorry, that's what I meant. I get it now. Thanks. I was looking at it back to front.
 
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
 
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
 

Similar threads

Undergrad Localizing single variable quotient polynomial ring at a prime ideal
  • · Replies 6 ·
Replies
6
Views
2K
Undergrad Trouble understanding an online solution to an exercise in Dummit & Foote
  • · Replies 21 ·
Replies
21
Views
3K
Undergrad Localising a non integral domain at a prime
  • · Replies 17 ·
Replies
17
Views
3K
Undergrad How to show ##p(x)=g(x)x\pm 1\in\Bbb{Q}[x]## is irreducible in ##\Bbb{Q}_{\Bbb{Z}}[x]##?
  • · Replies 48 ·
2
Replies
48
Views
7K
Undergrad Frequency of prime number gaps according to (p-1)/(p-2)
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad ##(A/\mathfrak{a})_{\mathfrak{p}/\mathfrak{a}}## and its isomorphism?
  • · Replies 31 ·
2
Replies
31
Views
4K
Undergrad Meaning of ##\coprod_{x\in\mathrm{Spec}R}R/\mathfrak{p}_x##
  • · Replies 11 ·
Replies
11
Views
2K
Undergrad Fundamental theorem of arithmetic from Jordan-Hölder theorem
  • · Replies 5 ·
Replies
5
Views
3K
Undergrad Understanding the Results of gcd(x,n)
  • · Replies 8 ·
Replies
8
Views
2K
Undergrad How to Prove a Congruence Relation for Prime Numbers?
  • · Replies 17 ·
Replies
17
Views
2K