Can two Mersenne numbers share a factor?

James Heinrich · 2011-09-04, 16:00

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?

axn · 2011-09-04, 16:02

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.

aketilander · 2011-09-05, 14:32

... 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?

petrw1 · 2011-09-05, 17:13

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.

R.D. Silverman · 2011-09-05, 17:20

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.

science_man_88 · 2011-09-05, 17:46

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.

Mini-Geek · 2011-09-05, 17:47

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 2p₁p₂+1. Nothing there suggests that it couldn't possibly divide both Mp₁ and Mp₂.
As axn already correctly stated, no two prime-exponent Mersenne numbers share a factor. It's just not suggested by 2kp+1.

petrw1 · 2011-09-06, 02:59

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 2p₁p₂+1. Nothing there suggests that it couldn't possibly divide both Mp₁ and Mp₂.
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?

axn · 2011-09-06, 03:38

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)

LaurV · 2011-09-06, 08:20

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 2^a-1 and 2^b-1, with a and b not necessarily prime, a>b, then it divides their difference too, which should be 2^a-1-2^b+1, or 2^b(2^a-b-1). As k is odd, it can't divide 2^b, so it divides the parenthesis. Repeating the process with 2^a-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, 2¹⁵-1 and 2²⁸-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 2^pa-1 and 2^pb-1 are divisible (algebrically) by 2^p-1.

Mini-Geek · 2011-09-06, 11:53

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.

2011-09-04, 16:00	#1
James Heinrich "James Heinrich" May 2004 ex-Northern Ontario 110101001110₂ 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-05, 14:32	#3
aketilander "Åke Tilander" Apr 2011 Sandviken, Sweden 1000110110₂ 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-06, 08:20	#10
LaurV Romulan Interpreter Jun 2011 Thailand 7×1,373 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 2^a-1 and 2^b-1, with a and b not necessarily prime, a>b, then it divides their difference too, which should be 2^a-1-2^b+1, or 2^b(2^a-b-1). As k is odd, it can't divide 2^b, so it divides the parenthesis. Repeating the process with 2^a-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, 2¹⁵-1 and 2²⁸-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 2^pa-1 and 2^pb-1 are divisible (algebrically) by 2^p-1. Last fiddled with by LaurV on 2011-09-06 at 08:40

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

2011-09-05, 17:13	#4
petrw1 1976 Toyota Corona years forever! "Wayne" Nov 2006 Saskatchewan, Canada 2²·7·167 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.