Exercise 2.8.37* ($n \nmid 2^n -1$)

Proof. Assume for contradiction that $n\mid 2^n-1$, where $n>1$.

Since $n>1$, $n$ has prime divisors. Let $p$ be the least prime divisor of $n$. Note that $p\ne 2$, otherwise, $2\mid n$, thus $2\mid 2^n-1$, but $2^n-1$ is odd. This is a contradiction, so $p\ne 2$.

If $q$ is any common prime factor of $p-1$ and $n$, then $q\mid n$, thus $q\ge p$ by definition of $p$, and $q\mid p-1$, therefore $q\le p-1<p$. This is a contradiction, so $p-1$ and $n$ have no common prime factor. This proves that $(p-1)\wedge n=1$.

Let $h$ be the order of $2$ modulo $p$. From $p\mid n$, and $n\mid 2^n-1$, we deduce $2^n\equiv 1(\mathit{mod}p)$. Therefore $h\mid n$. Moreover, by Fermat’s Theorem, $2^{p-1}\equiv 1(\mathit{mod}p)$, because $p\nmid 2$. Hence $h\mid p-1$. From $h\mid n$ and $h\mid p-1$, we deduce $h\mid n\wedge (p-1)=1$, thus $h=1$. Then $2^h=2\equiv 1(\mathit{mod}p)$, therefore $p\mid 1$. But $p$ is prime, so $p\nmid 1$. This is a contradiction, which proves that $n\nmid 2^n-1$ for every $n>1$. □