Results 1 to 4 of 4

Thread: Divisibility Problem(2)

  1. #1
    Junior Member
    Joined
    Mar 2010
    Posts
    63

    Divisibility Problem(2)

    Show that if $\displaystyle n>1$ is an integer, then $\displaystyle n$ does not divide $\displaystyle 2^n-1$.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485
    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$.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Jan 2009
    Posts
    715
    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 $ .
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. problem with divisibility
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Sep 8th 2010, 08:06 AM
  2. A divisibility problem
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: Aug 19th 2010, 08:21 PM
  3. A problem about divisibility
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Jul 29th 2010, 09:18 PM
  4. divisibility problem?
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Feb 24th 2010, 04:18 AM
  5. help this divisibility problem
    Posted in the Algebra Forum
    Replies: 1
    Last Post: Apr 29th 2008, 05:13 AM

Search Tags


/mathhelpforum @mathhelpforum