1. ## Divisibility Problem(2)

Show that if $\displaystyle n>1$ is an integer, then $\displaystyle n$ does not divide $\displaystyle 2^n-1$.

2. A simple case for primes $\displaystyle p$:

By Fermat's Little Theorem, $\displaystyle 2^p-1\equiv 2-1\equiv 1\pmod{p}$. Therefore, $\displaystyle p$ does not divide $\displaystyle 2^p-1$.

3. 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$ .

4. 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.