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?

[QUOTE=James Heinrich;270815]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?[/QUOTE]

GCD(2^a-1,2^b-1)=2^GCD(a,b)-1. So, for prime exponent mersennes, the answer is no.

Are all primes ±1 mod 8 factors?
 

... and then you could ask yourself if all primes of the form [FONT=Times New Roman]±1 mod 8 are a factor to a specific prime exponent Mersenne number each? :smile:[/FONT]

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.

[QUOTE=petrw1;270889]Mersenne factors are of the form (2k^p)+1.
[/QUOTE]
False.

[QUOTE]
Where p is the mersenne prime and k is any whole, positive number.

That would suggest that cannot be duplicated.[/QUOTE]

And false again.

[QUOTE=R.D. Silverman;270890]False.



And false again.[/QUOTE]

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.

[QUOTE=petrw1;270889]Mersenne factors are of the form (2k^p)+1. [/QUOTE]
That's 2kp+1.
[QUOTE=petrw1;270889]Where p is the mersenne prime and k is any whole, positive number.

That would suggest that cannot be duplicated.[/QUOTE]

Not really. Consider 2p[SUB]1[/SUB]p[SUB]2[/SUB]+1. Nothing there suggests that it couldn't possibly divide both Mp[SUB]1[/SUB] and Mp[SUB]2[/SUB].
As axn already correctly stated, no two prime-exponent Mersenne numbers share a factor. It's just not suggested by 2kp+1.

[QUOTE=Mini-Geek;270893]That's 2kp+1.[/QUOTE]

Oops. Yes that's what I meant. I was in too much of a hurry this AM.

[QUOTE]Not really. Consider 2p[SUB]1[/SUB]p[SUB]2[/SUB]+1. Nothing there suggests that it couldn't possibly divide both Mp[SUB]1[/SUB] and Mp[SUB]2[/SUB].
As axn already correctly stated, no two prime-exponent Mersenne numbers share a factor. It's just not suggested by 2kp+1.[/QUOTE]

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?

[QUOTE=petrw1;270925]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?[/QUOTE]

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)

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

For example, assuming k divides 2[SUP]a[/SUP]-1 and 2[SUP]b[/SUP]-1, with a and b not necessarily prime, a>b, then it divides their difference too, which should be 2[SUP]a[/SUP]-1-2[SUP]b[/SUP]+1, or 2[SUP]b[/SUP](2[SUP]a-b[/SUP]-1). As k is odd, it can't divide 2^b, so it divides the parenthesis. Repeating the process with 2[SUP]a-b[/SUP]-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[SUP]15[/SUP]-1 and 2[SUP]28[/SUP]-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 [B]never[/B] share a common factor. Except of course in the obvious case when their exponent share a common factor.:smile: In this case both 2[SUP]pa[/SUP]-1 and 2[SUP]pb[/SUP]-1 are divisible (algebrically) by 2[SUP]p[/SUP]-1.

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

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.