Can two Mersenne numbers share a factor?

[R.D. Silverman]

Originally Posted by petrw1

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



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?

I already told you that this was false. Did you think that I was lying??

[science_man_88]

Originally Posted by petrw1

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



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?

one thing I'd note:

1)2 isn't a mersenne number

so:

2) it can't be a mersenne prime.

[science_man_88]

Originally Posted by science_man_88

one thing I'd note:

1)2 isn't a mersenne number

so:

2) it can't be a mersenne prime.

also for your memory:

(11:36)>P=5%6;for(k=1,10,if((2*k*P+1)%6==1 || (2*k*P+1)%6==5,print(k%3)))
1
0
1
0
1
0
1
(11:36)>P=1%6;for(k=1,10,if((2*k*P+1)%6==1 || (2*k*P+1)%6==5,print(k%3)))
2
0
2
0
2
0

[chris2be8]

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?

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.

I think this is also true in any base. Ie for base b and exponents a and c (b^a-1)/(b-1) and (b^c-1)/(b-1) can't have common factors unless a and c do.

Am I right?

Chris K

[R.D. Silverman]

Originally Posted by chris2be8

I think this is also true in any base. Ie for base b and exponents a and c (b^a-1)/(b-1) and (b^c-1)/(b-1) can't have common factors unless a and c do.

Am I right?

Chris K

Hint: Look at the proof for GCD(2^a-1, 2^b-1)

[Christenson]

Originally Posted by R.D. Silverman

I already told you that this was false. Did you think that I was lying??

No, Petrw1 was afraid he might be putting forth more nonsense.... Only John Fullspeed thinks we lie here.

[only_human]

Originally Posted by chris2be8

I think this is also true in any base. Ie for base b and exponents a and c (b^a-1)/(b-1) and (b^c-1)/(b-1) can't have common factors unless a and c do.

Am I right?

Chris K

I am not sure you are right. Looking at the more restrictive case of (b^p-1)/(b-1) for prime p, possible factors are p (if p divides (b - 1)), or kp + 1 (for some integer k). This I read (to the best of my ability) in Chris Caldwell's paper "An Amazing Prime Heuristic" in the section that addresses generalized repunits.

I haven't thought out the consequences of factors of b-1

I am thinking about what k can equal. When a and c are prime, if k can be one of them while p is the other and this is true for both (b^a-1)/(b-1) and (b^c-1)/(b-1), then they could have a common factor.

My opinion is likely wrong due to a combination of enthusiasm and ignorance and is best to let it linger a while until someone smarter feels like pointing out a fallacy or two in it or lets it lie in politely ignored ignominy.

[axn]

Originally Posted by only_human

I am not sure you are right.

Originally Posted by R.D. Silverman

Hint: Look at the proof for GCD(2^a-1, 2^b-1)

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?

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.

Try to generalize LaurV's approach to arbitrary (non-power) base.

[R.D. Silverman]

Originally Posted by axn

Try to generalize LaurV's approach to arbitrary (non-power) base.

Enough already! Trivial counter examples can be found.

consider B = (b^3-1)/(b-1). Any b = 1 mod 3 will have B divisible by 3......
e.g. b = 7,10,13,.......

[axn]

Originally Posted by R.D. Silverman

Enough already! Trivial counter examples can be found.

consider B = (b^3-1)/(b-1). Any b = 1 mod 3 will have B divisible by 3......
e.g. b = 7,10,13,.......

I thought we were discussing generalizing to arbitrary base -- i.e. for a _given_ base, and varying exponents, we look for common factors. You've given fixed exponent and varying bases, which is not the same. What am I missing?

[LaurV]

I don't think you are missing something. We were talking about repunits in a given base. They are of the form (2ⁿ-1)/1 (decimal) if the base is 2, or (7ⁿ-1)/6 (decimal) = 666....6666/6₇ = 1111..1111₇ if the base is 7, and so on.

The question was if two repunits in a base b (fixed) can have a common factor, beside of the obvious case when the numbers of 1's in each repunit have a common factor themselves.

If the number of 1's is not prime, but some m*n, for sure we can factor it by grouping the digits in groups of m or n. For example 111111 in base 7 (=117648/6=19608 decimal) can be grouped like "11 11 11", or it can be grouped like "111 111" and therefore is divisible by 8 (7+1, not prime) and by 57 (7²+7+1, not prime). Because we can "subtract" a group of m (or n digits), shift left by m (or n) until we prove that the repunit is divisible by a group of m (or n) digits. Possible by some other factors too (in this case 43, prime).

So, for such a repunit to be prime, a necessary condition is that the number of one's in it to be prime (this is not sufficient, in fact, we don't know any sufficient condition, in reasonable terms, otherwise we could find primes very fast!).

The question is if two repunits in the SAME, FIXED base, can have common factors.

If the numbers of their digits share a common factor (that is, the exponents share a common factor) k, then you can split each repunit in groups of k units, and both of them would be divisible by (b^k-1)/(b-1).

Like (5¹²-1)/4 = 111 111 111 111₍₅₎= 61035156 = 2²*3²*7*13*31*601
and (5¹⁵-1)/4 = 111 111 111 111 111₍₅₎ = 7629394531 =11*31*71*181*1741

both share the factor 5³-1 = 31, because 12 and 15 share the factor 3, so we could split them in groups of 3 units each.

What happens when the numbers of 1's in them have no common factor? The answer should not be so difficult.