If $p\mid 2^n-1$ , then how to prove $l(n) \lt p$ If $n\in \Bbb N $,$ n \gt 1$ and $p$ is prime number such that $p\mid 2^n-1$ , then how to prove $l(n) \lt p$.
$l(n)$ is smallest of prime divisor $n$.
 A: Hint $\, \ \rm mod\ p\!:\ 2^{p-1}\!\equiv 1\equiv 2^{n}\Rightarrow\, 2^{(p-1,n)}\!\equiv 1,\:$ but the gcd $\rm\:(p\!-\!1,n) = 1\:$ if $\rm\:p \le {\it l}\,(n). \:$
Remark $\ $ Equivalently, mod $\rm\, p\!:\ 2^{p-1}\!\equiv 1\:\Rightarrow\:p\!-\!1\ge k:= $ order of $\,2.\:$ $\rm\:k\ne 1,\:$ else $\rm\:p\mid 2^{\,1}\!-\!1 = 1.\:$ $\rm\:2^n\!\equiv 1\,\Rightarrow\,k\mid n\,\Rightarrow\,k > $ least proper divisor of $\rm\:n, \:$ i.e. $\rm\,k > {\it l}\,(n).\:$ Thus $\rm\:p>p\!-\!1\ge k\ge {\it l}\,(n).$
A: Write $n = p_1^{l_1} p_2^{l_2} \cdots p_k^{l_k}$. Trivially $2^n \equiv 1 (p)$, since $p \mid 2^n - 1$.
Now, $\text{ord}_p(2) \mid n$ implies that some $p_i \mid \text{ord}_p(2)$.
According to Lagrange, $p_i \mid p - 1$ and, hence, $p_i < p - 1 < p$. 
Clearly, $l(n) \leq p_i$ for all $i$.
Paul Erdős enjoyed using this, when $n$ is prime, to prove the infinitude of primes.
A: $2^n-1$= $(2-1)(2^{n-1}+2^{n-2}+\cdots +1)$
If, $n=ab$ , Such that $a$ and $b$ are two prime divisors. W.L.O.G we can assume $a>b$
$$2^ {ab} -1= (2^a)^b-1 = (2^a-1)((2^a)^{b-1}+(2^a)^{b-2}+(2^a)^{b-3}+\cdots +2^a)$$
$$=(2^b)^a-1 = (2^b-1)((2^b)^{a-1}+(2^b)^{a-2}+(2^b)^{a-3}+\cdots +2^b)$$
But $2^a-1$ and $2^b-1$ are a $primes$. (Mersenne Primes).
$$l(n)=a$$
When, 
$$2^a-1=p$$
$$l(n)<p$$
When, 
$$2^b-1=p'$$
$$l(n)<p$$
We can prove general case! Taking $n=a_1a_2a_3a_4\cdots a_n$.
