mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2015-05-31, 00:33   #1
wildrabbitt
 
Jul 2014

22·3·37 Posts
Default 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.
wildrabbitt is offline   Reply With Quote
Old 2015-05-31, 01:01   #2
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

2×13×443 Posts
Default

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
ewmayer is offline   Reply With Quote
Old 2015-05-31, 01:51   #3
wildrabbitt
 
Jul 2014

22·3·37 Posts
Default

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.
wildrabbitt is offline   Reply With Quote
Old 2015-05-31, 02:12   #4
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

53·73 Posts
Default

There is a good page here, and in particular by following a link from Theorem Three, you will find this.
Batalov is offline   Reply With Quote
Old 2015-05-31, 02:25   #5
TheMawn
 
TheMawn's Avatar
 
May 2013
East. Always East.

11·157 Posts
Default

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.
TheMawn is offline   Reply With Quote
Old 2015-05-31, 13:13   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by wildrabbitt View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2015-05-31, 13:17   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11101001001002 Posts
Default

Quote:
Originally Posted by wildrabbitt View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2015-05-31, 15:30   #8
wildrabbitt
 
Jul 2014

22×3×37 Posts
Default

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.
wildrabbitt is offline   Reply With Quote
Old 2015-05-31, 15:46   #9
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11101001001002 Posts
Default

Quote:
Originally Posted by wildrabbitt View Post
"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".
R.D. Silverman is offline   Reply With Quote
Old 2015-05-31, 15:52   #10
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by wildrabbitt View Post
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.
science_man_88 is offline   Reply With Quote
Old 2015-05-31, 15:54   #11
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
Though I suck at language I'm going to disagree because numbers could include exponents which are not natural numbers.
Typical gibberish from you.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Room Temperature Alloy a1call Lounge 0 2017-05-20 14:34
Good air-cooler good enough for overclocked i7-5820K RienS Hardware 17 2014-11-18 22:58
IRC room? kracker Lounge 3 2012-06-17 20:59
experimental chip delivers 350 GHz @ room temp. ixfd64 Hardware 12 2007-09-21 14:14
Any room for optimization on Core 2 processors? E_tron Software 4 2007-03-30 06:59

All times are UTC. The time now is 19:53.

Mon Sep 21 19:53:51 UTC 2020 up 11 days, 17:04, 1 user, load averages: 2.71, 2.36, 2.22

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.