Least prime factor of $n$ is less than the least prime factor of $2^n-1$

Question

Let $O(n)$ be the least prime factor of $n$ and $O(1):=1$.

Prove that $O(n) < O(2^n-1)$. In particular, $p<O(2^p-1)$ with a prime number $p$.

I tried it so much but failed.

We can see that it is trivial if $n$ is even. The inequality also implies that the number of primes is infinite.

Answer 1

With $n \gt 1$, let

$$O(n) = p_1, \; O(2^n - 1) = p_2 \tag{1}\label{eq1A}$$

Next, let

$$m = \operatorname{ord}_{p_2}(2) \tag{2}\label{eq2A}$$

be the multiplicative order of $2$ modulo $p_2$. Since $m \gt 1$ and $2^n \equiv 1 \pmod{p_2}$, we have

$$m \mid n \implies m \ge p_1 \tag{3}\label{eq3A}$$

Since $p_2$ is odd, Fermat's little theorem gives

$$2^{p_2 - 1} \equiv 1 \pmod{p_2} \implies p_2 \gt m \tag{4}\label{eq4A}$$

Next, \eqref{eq4A} and \eqref{eq3A} together gives

$$p_2 \gt p_1 \implies p_1 \lt p_2 \tag{5}\label{eq5A}$$

Thus, the least prime factor of $n$ is less than that of $2^n - 1$, i.e.,

$$O(n) \lt O(2^n - 1) \tag{8}\label{eq8A}$$

Answer 2

For primes it is true. As this text (Theorem 1) shows all divisors of $2^p-1$ have the form $2pk+1$. Hence $O(p)<O(2^p-1)$ if $p$ is prime.