mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2011-09-04, 16:00   #1
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

2×5×353 Posts
Default Can two Mersenne numbers share a factor?

Is it possible for two composite Mersenne numbers to have a common factor?

In the 33,415,185 factors I've looked at there are no duplicates, but I don't know if this is by chance or guaranteed?
James Heinrich is offline   Reply With Quote
Old 2011-09-04, 16:02   #2
axn
 
axn's Avatar
 
Jun 2003

5,179 Posts
Default

Quote:
Originally Posted by James Heinrich View Post
Is it possible for two composite Mersenne numbers to have a common factor?

In the 33,415,185 factors I've looked at there are no duplicates, but I don't know if this is by chance or guaranteed?
GCD(2^a-1,2^b-1)=2^GCD(a,b)-1. So, for prime exponent mersennes, the answer is no.
axn is offline   Reply With Quote
Old 2011-09-05, 14:32   #3
aketilander
 
aketilander's Avatar
 
"Åke Tilander"
Apr 2011
Sandviken, Sweden

2×283 Posts
Default Are all primes ±1 mod 8 factors?

... and then you could ask yourself if all primes of the form ±1 mod 8 are a factor to a specific prime exponent Mersenne number each?

Last fiddled with by aketilander on 2011-09-05 at 14:48
aketilander is offline   Reply With Quote
Old 2011-09-05, 17:13   #4
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

12E616 Posts
Default

Mersenne factors are of the form (2k^p)+1.
Where p is the mersenne prime and k is any whole, positive number.

That would suggest that cannot be duplicated.
petrw1 is offline   Reply With Quote
Old 2011-09-05, 17:20   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by petrw1 View Post
Mersenne factors are of the form (2k^p)+1.
False.

Quote:
Where p is the mersenne prime and k is any whole, positive number.

That would suggest that cannot be duplicated.
And false again.
R.D. Silverman is offline   Reply With Quote
Old 2011-09-05, 17:46   #6
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
False.



And false again.
I thought this was already talked about by Silverman and others they said if I remember that all you need is 2*k*p1*p2+1 I think this simplifies into 2*u*p1 +1 where u=k*p2.
science_man_88 is offline   Reply With Quote
Old 2011-09-05, 17:47   #7
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

3·1,423 Posts
Default

Quote:
Originally Posted by petrw1 View Post
Mersenne factors are of the form (2k^p)+1.
That's 2kp+1.
Quote:
Originally Posted by petrw1 View Post
Where p is the mersenne prime and k is any whole, positive number.

That would suggest that cannot be duplicated.
Not really. Consider 2p1p2+1. Nothing there suggests that it couldn't possibly divide both Mp1 and Mp2.
As axn already correctly stated, no two prime-exponent Mersenne numbers share a factor. It's just not suggested by 2kp+1.

Last fiddled with by Mini-Geek on 2011-09-05 at 17:49
Mini-Geek is offline   Reply With Quote
Old 2011-09-06, 02:59   #8
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

113468 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
That's 2kp+1.
Oops. Yes that's what I meant. I was in too much of a hurry this AM.

Quote:
Not really. Consider 2p1p2+1. Nothing there suggests that it couldn't possibly divide both Mp1 and Mp2.
As axn already correctly stated, no two prime-exponent Mersenne numbers share a factor. It's just not suggested by 2kp+1.
Feel free to correct me again but if I recall my analysis correctly ... in the above formula k is always an even number so it can't be a mersenne prime (other than 2 of course). And wouldn't this also show that a factor cannot be duplicated?
petrw1 is offline   Reply With Quote
Old 2011-09-06, 03:38   #9
axn
 
axn's Avatar
 
Jun 2003

5,179 Posts
Default

Quote:
Originally Posted by petrw1 View Post
Feel free to correct me again but if I recall my analysis correctly ... in the above formula k is always an even number so it can't be a mersenne prime (other than 2 of course). And wouldn't this also show that a factor cannot be duplicated?
Even if k is always an even number (which it needn't be), 2kp1p2+1 can be rewritten as 2Kp1+1 or 2Kp2+1 (where K=kp1 or K=kp2 will also be an even number, since even * odd = even)
axn is offline   Reply With Quote
Old 2011-09-06, 08:20   #10
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

24×613 Posts
Default

Actually... if we start making gcd's, then a stronger affirmation could be true, isn't is? like "two mersenne numbers with coprime exponents can not share the same factor". Or am I wrong?

For example, assuming k divides 2a-1 and 2b-1, with a and b not necessarily prime, a>b, then it divides their difference too, which should be 2a-1-2b+1, or 2b(2a-b-1). As k is odd, it can't divide 2^b, so it divides the parenthesis. Repeating the process with 2a-b-1 and any one from the initially 2 mersenne involved, we could see that k divides 2^1-1=1, when gcd(a,b) is 1, as we already recognize the "gcd-ing" process for the exponents.

That is, 215-1 and 228-1 (substitute 15 and 28 with any 2 coprimes) can't have common factors, even if 15 and 28 are not primes. Particularly, the affirmation is true for primes, as they are always coprime.

If this reasoning is right and I am not missing something, then we can answer yes for the general case: two mersenne numbers never share a common factor. Except of course in the obvious case when their exponent share a common factor. In this case both 2pa-1 and 2pb-1 are divisible (algebrically) by 2p-1.

Last fiddled with by LaurV on 2011-09-06 at 08:40
LaurV is offline   Reply With Quote
Old 2011-09-06, 11:53   #11
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

3·1,423 Posts
Default

Quote:
Originally Posted by LaurV View Post
Actually... if we start making gcd's, then a stronger affirmation could be true, isn't is? like "two mersenne numbers with coprime exponents can not share the same factor". Or am I wrong?
Yep, this is right, implied by the formula GCD(2^a-1,2^b-1)=2^GCD(a,b)-1: If a and b are coprime, GCD(a,b)=1, so GCD(2^a-1,2^b-1) is also 1.
Mini-Geek is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Can Mersenne composites share "shape"? jnml Miscellaneous Math 31 2018-01-01 01:55
Small inconsistencies between mersenne.org and mersenne.ca factor databases GP2 mersenne.ca 44 2016-06-19 19:29
6 digit numbers and the mersenne numbers henryzz Math 2 2008-04-29 02:05
LLT numbers, linkd with Mersenne and Fermat numbers T.Rex Math 4 2005-05-07 08:25
P-1 factoring != "Mersenne numbers to factor"? James Heinrich Marin's Mersenne-aries 8 2004-05-17 11:09

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


Wed Dec 1 04:29:38 UTC 2021 up 130 days, 22:58, 1 user, load averages: 1.43, 1.26, 1.27

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.