# A question about prime divisors of Mersenne number $M_n= 2^n-1$ when $n$ is odd

Is this true that a prime divisor of a Mersenne number $M_n = 2^n-1$ when $n$ is odd, cannot be a Proth prime (i.e. a prime number of the form $2^mk+1$, where $k<2^m$)?

If yes, how is it demonstrated?

thank you!

because, if I am not wrong, for any prime $p>3$ ($= r2^v +1$, where $r$ is odd and $v>1$),
either there exists a unique $j < v-1$ so that $p$ is a divisor of $2^J+1$, where $J=r2^j$,
or $p$ is divisor of $2^r-1$.

In the latter case, whenever I have checked so far, if I write $p$ as $k2^m+1$, ($k$ odd) $k$ is larger than $2^m$. Is this always like that?

In the former case, most of the times $j$ is $v-2$ or a slightly smaller. In particular, so far I have checked, it is rather rare that $v$ and $j$ differ by more than say $5$, like for instance when $p=65537(j=4,v=16)$, or $p=59393(j=2,v=11)$, or $p=25601 (j=3,v=10)$, or $p=2113 (j=1,v=6)$ or $p=6529 (j=0,v=7)$... I wonder how many such prime numbers exist ?

• Why do you suspect this should be true? – Greg Martin Feb 19 '14 at 18:39

Interesting conjecture! It holds for quite some time...

... before failing at $n=225$. The corresponding Proth prime factor is $p=115201=225\times 2^9+1$. It's not too difficult to see that any odd multiple of $n$ would be a counter-example too, since the corresponding Mersenne number would be divisible by $p$ as well.

The next two non-trivial cases seem to be:

• $n=6281$ and $p=51453953=6281\times 2^{13}+1$
• $n=7695$ and $p=126074881=7695\times 2^{14}+1$

Interestingly, those are all the counter-examples I managed to find even after searching for quite some more time. It's not too surprising, though, since Proth primes are relatively rare.

• thank you for the counterexamples! I did not go that far... – René Gy Feb 20 '14 at 1:16
• it seems that $m$ is hardly much bigger than than the exponent in the biggest power of $2$ which is smaller than $n$... but again this should checked for the very big $n$... – René Gy Feb 20 '14 at 7:09