Show that if $\displaystyle n>1$ is an integer, then $\displaystyle n$ does not divide $\displaystyle 2^n-1$.
This is my attempt , i am not sure if it is correct . For me i find that i always make mistakes in the problems about number theory , logical errors , computational mistakes , etc .
Note that $\displaystyle n $ cannot be even , otherwise , $\displaystyle 2^n - 1 $ is odd which cannot have $\displaystyle 2 $ as its factor . In other words , $\displaystyle (2,n) = 1 $ .
Consider the case that we can find a number $\displaystyle n > 1 $ satisfying $\displaystyle 2^n - 1 = 1 + 2+ 2^2 + 2^3 + ... + 2^{n-1} \equiv 0 \bmod{n} $
. Also let $\displaystyle n $ be minimum .
As we know $\displaystyle n $ is odd , we have $\displaystyle 2^{\phi(n)} \equiv 1 \bmod{n} $ but note that it is not necessary of $\displaystyle \phi(n) $
to be the order so we can find the minimal $\displaystyle d|\phi(n)$ such that $\displaystyle 2^d - 1 \equiv 0 \bmod{n} $ , with a litte reminder $\displaystyle 1<d<n $ . If $\displaystyle d $ doesn't divide $\displaystyle n $ , write $\displaystyle n = pd + r ~,~ 0<r<d $ . We have
$\displaystyle (1+2+2^2 + ... + 2^{d-1} ) + (2^d + ... + 2^{2d-1} ) + ... + (2^{pd} + ... + 2^{pd+r-1} ) \equiv 0 \bmod{n} $
$\displaystyle (1+2+ 2^2 + ... + 2^{d-1} ) + (1+ ... + 2^{d-1} ) + ... + (1 + ... + 2^{r-1} ) \equiv 0 \bmod{n}$
$\displaystyle p (1+2+ 2^2 + ... + 2^{d-1} ) + (1 + ... + 2^{r-1} ) \equiv 0 \bmod{n}$
$\displaystyle p( 2^d - 1 ) + (2^r - 1 ) \equiv 0 \bmod{n} $
$\displaystyle 2^r \equiv 1 \bmod{n} $ which contradicts the minimality of $\displaystyle d $ .
Suppose $\displaystyle d | n $ , Then from $\displaystyle 2^d - 1\equiv 0 \bmod{n} $ implies that $\displaystyle 2^d - 1 \equiv 0 \bmod{d}$ .
But $\displaystyle d < n $ so it cannot equal $\displaystyle n $ , this also contradicts the minimality of $\displaystyle n $ .
I had this as a problem in the past, but in the contrapositive (which is equivalent) form: If $\displaystyle n|2^n-1$, then $\displaystyle n=1 $. (Incidentally, I was provided with a hint)
I want to offer another solution; I will use the following lemma: For positve integers $\displaystyle u $, $\displaystyle v $, and $\displaystyle n $, if $\displaystyle a^u\equiv1\bmod n$ and $\displaystyle a^v\equiv1\bmod n$, then $\displaystyle a^d\equiv1\bmod n$, where $\displaystyle d=(u,v)$.
Since $\displaystyle n>1 $, $\displaystyle n $ has a least prime divisor $\displaystyle p $. Suppose to the contrary that $\displaystyle 2^n\equiv1\bmod n$, then since $\displaystyle p|n $ we have $\displaystyle 2^n\equiv1\bmod p$.
By Fermat's Theorem, $\displaystyle 2^{p-1}\equiv 1\bmod p$. Now, according to the lemma it follows that $\displaystyle 2^d\equiv 1\bmod p$, where $\displaystyle d=(n,p-1)$.
We cannot have $\displaystyle d>1 $, because $\displaystyle d|n $ and also $\displaystyle 1<d<p $, but $\displaystyle p $ is the smallest divisor of $\displaystyle n $ that is greater than 1.
Thus, we're left with $\displaystyle d=1 $.
$\displaystyle 2^d=2^1\equiv1\bmod p$, which implies that $\displaystyle p|1 $, contradiction.