Prove that $\forall n > 1 \quad2^n - 1 \pmod n \neq 0$ Prove that $\forall n > 1, \quad2^n - 1 \pmod n \neq 0$
I've thought of the induction but I can't figure out how to prove the step. Fermat's theorem (and its variations) aren't particularly useful as well. Any hint would be greatly appreciated!
 A: Assume you have got a $n>1$, so that $2^n \equiv 1 \pmod{n}$. Take the smallest prime divisor $p$ of $n$.
You have $p\;|\;n\;|\;2^n-1$, hence $2^n\equiv 1 \pmod{p}$.
But you have also, from Fermat's little theorem, that $2^{p-1}\equiv 1\pmod{p}$.
Since $p-1$ and $n$ are coprime, you have thus by Bézout's identity, some $a,b$ such that $a(p-1)+bn=1$, and then
$$1\equiv(2^{p-1})^a\cdot (2^n)^b \equiv 2^{a(p-1)+bn}\equiv 2^1 \pmod{p}$$
Thus $2^1\equiv 1\pmod{p}$, or equivalently $p\;|\;1$, but this is not possible.
A: A counterexample $\,n\,$ i.e.  $\ n\mid 2^n-1\,$ would contradicts the more general theorem below.
Theorem $\,\ \ \ m,n>1,\,\ m\mid 2^{\large n}-1\,\Rightarrow\, \ell(m) > \ell(n),\ \ $   $\ell(x) =\,$ least prime factor of $\,x $ 
Proof $\quad\ \, {\rm mod}\,\ p = \ell(m)\!:\,\ 2^{\large n}\equiv 1\equiv\, 2^{\large\color{}{ p-1}}\,$ $\Rightarrow$ $\,\ \ell(m) = p > {\rm ord}\,2\color{#80f}{ \ge \ell(n)}$ 
Remark $\,\ $ The $ $ key dea $ $ is: $\ \  2^n\equiv 1,\,\ \color{#0a0}{2\not\equiv 1}\,$ implies the order of $\,2\,$ is $\,\color{#80f}{\ge\ {\rm least\  prime}\,\ q\mid n},\ $ because the order  must divide $\,n,\,$ and is $\color{}{\neq \color{#c00}1}$ (else $\,\color{#0a0}{2^{\color{#c00}{\large 1}}\equiv 1})$. 
