mersenneforum.org > Math Can two Mersenne numbers share a factor?
 Register FAQ Search Today's Posts Mark Forums Read

 2011-09-04, 16:00 #1 James Heinrich     "James Heinrich" May 2004 ex-Northern Ontario 2×5×7×53 Posts 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?
2011-09-04, 16:02   #2
axn

Jun 2003

23·233 Posts

Quote:
 Originally Posted by James Heinrich 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.

 2011-09-05, 14:32 #3 aketilander     "Åke Tilander" Apr 2011 Sandviken, Sweden 56610 Posts 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
 2011-09-05, 17:13 #4 petrw1 1976 Toyota Corona years forever!     "Wayne" Nov 2006 Saskatchewan, Canada 143D16 Posts 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.
2011-09-05, 17:20   #5
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by petrw1 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.

2011-09-05, 17:46   #6
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by R.D. Silverman 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.

2011-09-05, 17:47   #7
Mini-Geek
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

10B516 Posts

Quote:
 Originally Posted by petrw1 Mersenne factors are of the form (2k^p)+1.
That's 2kp+1.
Quote:
 Originally Posted by petrw1 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

2011-09-06, 02:59   #8
petrw1
1976 Toyota Corona years forever!

"Wayne"
Nov 2006

3·11·157 Posts

Quote:
 Originally Posted by Mini-Geek 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?

2011-09-06, 03:38   #9
axn

Jun 2003

23×233 Posts

Quote:
 Originally Posted by petrw1 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)

 2011-09-06, 08:20 #10 LaurV Romulan Interpreter     "name field" Jun 2011 Thailand 2·17·293 Posts 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
2011-09-06, 11:53   #11
Mini-Geek
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

10000101101012 Posts

Quote:
 Originally Posted by LaurV 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post jnml Miscellaneous Math 31 2018-01-01 01:55 GP2 mersenne.ca 44 2016-06-19 19:29 henryzz Math 2 2008-04-29 02:05 T.Rex Math 4 2005-05-07 08:25 James Heinrich Marin's Mersenne-aries 8 2004-05-17 11:09

All times are UTC. The time now is 17:47.

Fri May 20 17:47:23 UTC 2022 up 36 days, 15:48, 0 users, load averages: 1.44, 1.60, 1.53