Are Mersenne Pseudoprimes are all Relatively Prime?
 

In other words can any 2 Mersenne numbers with prime exponents share a factor other than 1?
I think not, but have no proof.
Note that the fact that all the factors have the form 2kp+1 is not sufficient condition by itself, since the k from one can be a product of the p from the other.
Are there any proofs/counterexamples?
Thank you for your time.:smile:

[QUOTE=a1call;493294]In other words can any 2 Mersenne numbers with prime exponents share a factor other than 1?
I think not, but have no proof.[/QUOTE]

gcd(2^m - 1, 2^n - 1) = 2^gcd(m, n) - 1, so if p and q are distinct primes then gcd(2^p - 1, 2^q - 1) = 1.

[QUOTE=a1call;493294]
Are there any proofs/counterexamples?[/QUOTE]
Sure, [TEX]2^p-1=2^{p-q}(2^q-1)+(2^{p-q}-1)[/TEX] this, along with Euler's gcd algorithm shows it wouldn't be the first, and it's possible to use repetition until you hit the smallest mersenne.

[QUOTE=CRGreathouse;493296]gcd(2^m - 1, 2^n - 1) = 2^gcd(m, n) - 1, so if p and q are distinct primes then gcd(2^p - 1, 2^q - 1) = 1.[/QUOTE]

Very interesting GCD arithmetic and a very intelligent proof.:smile:

Did you just come up with it?

:bow wave:

ETA So if I'm not mistaking the statement can be generalized to:


[QUOTE]gcd(2^m - 1, 2^n - 1) = 2^gcd(m, n) - 1, so if p and q are [B]coprime [/B]then gcd(2^p - 1, 2^q - 1) = 1.[/QUOTE]Is that correct?

[QUOTE=a1call;493324]Is that correct?[/QUOTE]

Yes -- though I wouldn't use p and q unless they were prime, I'd use something like m and n. :smile:

It follows that for all primes p and q:
gcd(p,Mp)=1

and:

q | Mp => Mp | (2^q-2)

:smile:

It follows that for all primes p and q:
gcd(p,Mp)=1

and:

q | Mp => Mp | (Mq-1)

:smile:

Does anyone else see a Mersenne Pseudoprimes factoring routine in there?
I'm getting too old for this.
To find the factor q of Mp, find power of 2 subtracted by 2 which is divisible by Mp.
Mod (2,Mp)^n progresses predictably for incrementation of n and can be formulated rather than brute forced to find n=q.
Any comments?

Neat, proof?

[QUOTE=CRGreathouse;493347]Neat, proof?[/QUOTE]

Sure, why not.:smile:
Will be appreciated.

[QUOTE=a1call;493345]
To find the factor q of Mp, find power of 2 subtracted by 2 which is divisible by Mp.
Mod (2,Mp)^n progresses predictably for incrementation of n and can be formulated rather than brute forced to find n=q.
[/QUOTE]
And by extension provide an alternative (to LL Test) primality for Mersenne primes by establishing that the smallest non unity factor is equal to the candidate Mersenne prime.
I'm hoping someone will do the proof of concept coding so that I don't have to.:smile: