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

Printable View

- Sep 17th 2010, 09:21 PMMarkeurDivisibility Problem(2)
Show that if $\displaystyle n>1$ is an integer, then $\displaystyle n$ does not divide $\displaystyle 2^n-1$.

- Sep 17th 2010, 11:50 PMroninpro
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$. - Sep 18th 2010, 02:40 AMsimplependulum
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 $ . - Sep 18th 2010, 01:02 PMmelese
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.