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

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 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.

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

• Thanks a lot for the nice proof by using multiplicative order of 2 here. Oct 12, 2020 at 1:18
• @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. 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) if $$p$$ is prime.