mersenneforum.org Good mathematical tinkerers are in the Zen room
 Register FAQ Search Today's Posts Mark Forums Read

 2015-05-31, 00:33 #1 wildrabbitt   Jul 2014 3×149 Posts Good mathematical tinkerers are in the Zen room Hi, we all probably know that 2^p -1 are mostly composite but I'd like to know a reason why some are prime. I guess a proof by contradiction might prove this. Can someone suggest anything? I'd be very grateful for any suggestions, thoughts.
 2015-05-31, 01:01 #2 ewmayer ∂2ω=0     Sep 2002 República de California 2·3·1,931 Posts Speaking roughly at the grade-school math level: - They're all odd and no 'these cannot possibly be prime' condition (as e.g. for odd-composite-exponent 2^n-1) applies to them, thus (naively) have at least the same odds of being prime as a randomly chosen odd number. - Less naively, the special form of the possible factors q of 2^p-1 (q = 2*k*p+1) greatly restricts the candidate odd numbers which can possibly divide 2^p-1, so in fact a randomly chosen 2^p-1 has far greater odds of being prime than a randomly chosen odd number-of-no-special-algebraic-form of similar size. Note that there are good heuristic reasons to expect both an oo number of M-primes to exist and further as to their large-scale statistical distribution (the avg M-prime has p roughly 1.4x larger than its immediate predecessor), but no rigorous proofs along these lines. Last fiddled with by ewmayer on 2015-05-31 at 01:02
 2015-05-31, 01:51 #3 wildrabbitt   Jul 2014 6778 Posts Can you point me to a proof of the necessary form of a prime factor of a composite, prime-exponent Mersenne number?? Thanks for the reply.
 2015-05-31, 02:12 #4 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 926310 Posts There is a good page here, and in particular by following a link from Theorem Three, you will find this.
 2015-05-31, 02:25 #5 TheMawn     May 2013 East. Always East. 11·157 Posts That is actually a very interesting question. Like you say, there are examples by contradiction (48 of them, to be precise ) but all that really tells us is that there is no possible proof that there can't be any Mersenne primes. If we took a different number form, say [a * (b + c + 1) + (d * e) - 1] for any positive integers a, ..., e > 1, as something I have literally made up on the spot, and ask "can there possibly be any prime numbers of this form?", I don't think there's much we can do about it. It's more like the opposite: Prove that there can't be any primes and assume until then that we can have primes.
2015-05-31, 13:13   #6
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by wildrabbitt Hi, we all probably know that 2^p -1 are mostly composite
What does it mean for a number to be "mostly composite"?

I think you mean that most 2^p-1 are composite. If you want to do mathematics
you have to learn the correct use of quantifiers.

Quote:
 but I'd like to know a reason why some are prime.
Two reasons. You will not understand the second until you study some analytic number
theory. No disrespect intended, but you don't know enough math.

(1) 2^p-1 does not have any algebraic factors that force it to be composite.
Consider instead, x^p-1, for p prime. Since p = 2k+1 for some k, we have the algebraic
factor (x-1) of (x^(2k+1) - 1). Now, when x equals 2, this algebraic factor has the value
1 whereas for all other x > 1, the algebraic factor is non-trivial.

(2) sum from p=2 to infinity of 1/log(2^p-1) diverges.

The latter implies that there should be infinitely many Mersenne Primes via the Prime Number Theorem.

Quote:
 Can someone suggest anything? I'd be very grateful for any suggestions, thoughts.

2015-05-31, 13:17   #7
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by wildrabbitt Can you point me to a proof of the necessary form of a prime factor of a composite, prime-exponent Mersenne number?? Thanks for the reply.
You want q to divide 2^p-1, whence 2^p = 1 mod q.
Now apply Lagrange's Theorem.

2015-05-31, 15:30   #8
wildrabbitt

Jul 2014

3·149 Posts

Quote:
 The latter implies that there should be infinitely many Mersenne Primes via the Prime Number Theorem.
"could" not "should". Isn't that the right word? There is no proof right now that there are infinitely many Mersenne primes AFAIK.

Quote:
 we all probably know that 2^p -1 are mostly composite
Isn't it obvious I meant "we all probably know that numbers of the form 2^p -1 are mostly (said numbers) composite?

I have problems with plurality.

2015-05-31, 15:46   #9
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by wildrabbitt "could" not "should". Isn't that the right word? There is no proof right now that there are infinitely many Mersenne primes AFAIK.
No. "should" is correct. Although a proof is lacking, there exist very strong heuristic arguments.

Quote:
 Isn't it obvious I meant "we all probably know that numbers of the form 2^p -1 are mostly (said numbers) composite? I have problems with plurality.
Math is a language in which it is possible to say exactly what is meant. Colloquial English does
not apply. And your followup statement is still wrong. There is a difference between "numbers .... are mostly composite"
and "most numbers.... are composite".

I will offer a hint: In English, your wording would consist of a "misplaced modifier".

2015-05-31, 15:52   #10
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by wildrabbitt Isn't it obvious I meant "we all probably know that numbers of the form 2^p -1 are mostly (said numbers) composite?
Though I suck at language I'm going to disagree because numbers could include exponents which are not natural numbers.

2015-05-31, 15:54   #11
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by science_man_88 Though I suck at language I'm going to disagree because numbers could include exponents which are not natural numbers.
Typical gibberish from you.

 Similar Threads Thread Thread Starter Forum Replies Last Post a1call Lounge 0 2017-05-20 14:34 RienS Hardware 17 2014-11-18 22:58 kracker Lounge 3 2012-06-17 20:59 ixfd64 Hardware 12 2007-09-21 14:14 E_tron Software 4 2007-03-30 06:59

All times are UTC. The time now is 04:23.

Mon Jan 25 04:23:28 UTC 2021 up 53 days, 34 mins, 0 users, load averages: 2.10, 2.20, 2.19