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.


2 Answers 2


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}$$

  • 1
    $\begingroup$ Thanks a lot for the nice proof by using multiplicative order of 2 here. $\endgroup$ Oct 12, 2020 at 1:18
  • 1
    $\begingroup$ @NguyenDangSon You're welcome. I just updated my answer when I realized that, since $p_2$ is prime, I could simplify it somewhat by using Fermat's little theorem instead of Euler's theorem and Euler's totient function. $\endgroup$ Oct 12, 2020 at 1:31

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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .