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 ?

  • 2
    $\begingroup$ Why do you suspect this should be true? $\endgroup$ 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.

  • $\begingroup$ thank you for the counterexamples! I did not go that far... $\endgroup$
    – René Gy
    Feb 20 '14 at 1:16
  • $\begingroup$ 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$... $\endgroup$
    – René Gy
    Feb 20 '14 at 7:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.