Prove that $\forall n > 1, n \nmid 2^n-1$.

Question

$$\forall n > 1, n \nmid 2^n-1$$.

I have proved that this would not be divisible by some even $n$ but I'm unable to do it for odd $n$.

Answer 1

We can prove something stronger, let $p$ be the smallest prime dividing $n$, then $p$ does not divide $2^n -1$.

Notice that $2^n-1$ is a multiple of $p$ if and only if the order of $2\bmod p$ divides $n$, however the order of $2\bmod p$ is a divisor of $\varphi(p)$, and $\varphi(p)$ and $n$ are coprime.

This would imply the order of $2\bmod p$ is $1$ which would imply $p|(2-1) $