Results 1 to 4 of 4

Math Help - Divisibility Problem(2)

  1. #1
    Junior Member
    Joined
    Mar 2010
    Posts
    63

    Divisibility Problem(2)

    Show that if n>1 is an integer, then n does not divide 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 p:

    By Fermat's Little Theorem, 2^p-1\equiv 2-1\equiv 1\pmod{p}. Therefore, p does not divide 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  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<d<n . If  d doesn't divide  n , write  n = pd + r ~,~ 0<r<d . 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 .
    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 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<d<p , 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.
    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: September 8th 2010, 09:06 AM
  2. A divisibility problem
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: August 19th 2010, 09:21 PM
  3. A problem about divisibility
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: July 29th 2010, 10:18 PM
  4. divisibility problem?
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: February 24th 2010, 05:18 AM
  5. help this divisibility problem
    Posted in the Algebra Forum
    Replies: 1
    Last Post: April 29th 2008, 06:13 AM

Search Tags


/mathhelpforum @mathhelpforum