# Thread: Divisibility Problem(2)

1. ## Divisibility Problem(2)

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

2. A simple case for primes $p$:

By Fermat's Little Theorem, $2^p-1\equiv 2-1\equiv 1\pmod{p}$. Therefore, $p$ does not divide $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 $n$ cannot be even , otherwise , $2^n - 1$ is odd which cannot have $2$ as its factor . In other words , $(2,n) = 1$ .

Consider the case that we can find a number $n > 1$ satisfying $2^n - 1 = 1 + 2+ 2^2 + 2^3 + ... + 2^{n-1} \equiv 0 \bmod{n}$
. Also let $n$ be minimum .

As we know $n$ is odd , we have $2^{\phi(n)} \equiv 1 \bmod{n}$ but note that it is not necessary of $\phi(n)$
to be the order so we can find the minimal $d|\phi(n)$ such that $2^d - 1 \equiv 0 \bmod{n}$ , with a litte reminder $1 . If $d$ doesn't divide $n$ , write $n = pd + r ~,~ 0 . We have

$(1+2+2^2 + ... + 2^{d-1} ) + (2^d + ... + 2^{2d-1} ) + ... + (2^{pd} + ... + 2^{pd+r-1} ) \equiv 0 \bmod{n}$

$(1+2+ 2^2 + ... + 2^{d-1} ) + (1+ ... + 2^{d-1} ) + ... + (1 + ... + 2^{r-1} ) \equiv 0 \bmod{n}$

$p (1+2+ 2^2 + ... + 2^{d-1} ) + (1 + ... + 2^{r-1} ) \equiv 0 \bmod{n}$

$p( 2^d - 1 ) + (2^r - 1 ) \equiv 0 \bmod{n}$

$2^r \equiv 1 \bmod{n}$ which contradicts the minimality of $d$ .

Suppose $d | n$ , Then from $2^d - 1\equiv 0 \bmod{n}$ implies that $2^d - 1 \equiv 0 \bmod{d}$ .

But $d < n$ so it cannot equal $n$ , this also contradicts the minimality of $n$ .

4. I had this as a problem in the past, but in the contrapositive (which is equivalent) form: If $n|2^n-1$, then $n=1$. (Incidentally, I was provided with a hint)

I want to offer another solution; I will use the following lemma: For positve integers $u$, $v$, and $n$, if $a^u\equiv1\bmod n$ and $a^v\equiv1\bmod n$, then $a^d\equiv1\bmod n$, where $d=(u,v)$.

Since $n>1$, $n$ has a least prime divisor $p$. Suppose to the contrary that $2^n\equiv1\bmod n$, then since $p|n$ we have $2^n\equiv1\bmod p$.
By Fermat's Theorem, $2^{p-1}\equiv 1\bmod p$. Now, according to the lemma it follows that $2^d\equiv 1\bmod p$, where $d=(n,p-1)$.

We cannot have $d>1$, because $d|n$ and also $1, but $p$ is the smallest divisor of $n$ that is greater than 1.
Thus, we're left with $d=1$.
$2^d=2^1\equiv1\bmod p$, which implies that $p|1$, contradiction.