Lower Bound of a Factor of M = 2^P - 1, when M is a composite (P is prime).

Question

I was wondering, is there any rule for the smallest factor of M (where M = 2^P - 1, P is a prime) when M is composite.

I have an observation, I found the smallest factor for the following P:

P     Smallest Factor
11          23
23          47
29         233
37         223
59       179951
193     13821503

My question is Is there any lower bound on the smallest factor depending on P, From the observation we can see that the smallest factor > 2*P.

Answer 1

https://primes.utm.edu/glossary/page.php?sort=MersenneDivisor shows us that we have :

$$q|M_p\implies q=2kp+1$$, Which takes $k\equiv 0,-p\bmod 4$ to possibly be prime and 1 or 7 mod 8.

We also have via the second theorem that:$$p\equiv 3\bmod 4,q=2p+1\in \mathbb{P}\implies q| M_p$$ Which shows by congruence, that all $p$ in first kind Cunningham chains, unless $p\equiv 1\bmod 4$ which makes it at the beginning or, if it's at the end, are out as composite with $k=1$ . That or they aren't in a chain at all for Mersenne primes exponents.

Note

$(2kp+1)(2jp+1)=2(2kj+k+j)p+1$ like normal Sieve of sundaram on multiples of $p$

we can sieve out by smaller primes of course, if $k\equiv p\bmod 3$ then $2kp+1$ will be divisible ( exception $p=3$) by 3, in fact if ${r-1\over 2}\equiv kp\bmod r$ then $r$ divides $2kp+1$ This lets you sieve small k away. so we have two sieve of sundaram versions. In fact we could predict survivors if we knew where they were both null. but that seems a far way off. That's why GIMPS sieves by GPU TF, and modified P-1 test, and at last check was working on a PRP test, all before doing any LL testing. Arguably you can modify the LL test for testing for factors of known composites, but it's not really efficient.

Answer 2

If $p$ is odd then a prime factor $q$ of $2^p-1$ at least satisfies $q \equiv 1 \pmod {2p}$, so $q > 2p$. See here. That page also lists some examples where $2p+1 | 2^p-1$.

Answer 3

Let $p$ be an odd prime.

Then every factor of $M_{p}$ is primitive; that is, divides the Mersenne sequence for the very first time at that term.

Now, the sequence of Mersenne numbers is a Lucas sequence; and so, the properties that hold for the Lucas sequences also hold for the Mersenne numbers. However, whereas in general $p$ divides either the term with index $p-1$ or the term with index $p+1$ but not both, in the case of the Mersenne sequence $M_{k}$, we have $p | M_{p-1}$. (It cannot divide $M_{p+1}$).

Thus, the smallest factor of $M_{p}$ (where all the factors are primitive) must be some prime $q > p$, for it cannot be $p$ for $p$ divides $M_{p-1}$ and it cannot be a prime less than $p$ for an analogous reason.

And so, the smallest non-trivial value that may divide $M_{p}$ is $q = 2p + 1$, provided that $2p+1$ is prime and does not have what's called maximal rank of apparition (i.e., does not divide the Mersenne sequence for the first time at M_{2p}). That being the case, the rank of apparition (or rather, the order of $2$ mod $q$) must be a factor of $2p$. Since $q$ does not divide $M_{2} = 3$, the prime $2p+1$ must then divide $M_{p}$.

Succinctly stated, given $M_{p}$, its smallest possible non-trivial factor is $2p+1$, where $2p+1$ is prime. But that being said, if $2p+1$ is prime, that doesn't necessarily mean that it will divide $M_{p}$, but rather that it may divide $M_{p}$.

(It will divide it provided that the rank of apparition of the prime $2p+1$ is not maximal.)