Results 1 to 12 of 12

Math Help - Proof involving GCD

  1. #1
    Newbie
    Joined
    Oct 2009
    Posts
    12

    Proof involving GCD

    Prove that for any two positive integers n amd m,
    gcd(2^n - 1, 2^m -1) = 2^{gcd(n,m)}-1

    Not sure how to approach this problem .
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member Shanks's Avatar
    Joined
    Nov 2009
    From
    BeiJing
    Posts
    374
    let d=gcd(n,m), then there exist positive integers k,s, such that n=kd,m=sd,(k,s)=1.
    Obviously, 2^d-1 is a common divisor of the two number.
    And, it is easy to prove that 1+2^d+2^{2d}+...+2^{(k-1)d} and 1+2^d+2^{2d}+...+2^{(s-1)d} are relatively prime if (k,s)=1.
    thus the result is proved!
    Last edited by Shanks; November 30th 2009 at 10:08 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2009
    Posts
    12
    Thank you. I am confused though. Why do you wish to prove 1+2+2^2+...+2^k and 1+2+2^2+...+2^s are relatively prime?

    Also, why is it obvious that 2^d-1 is a factor of those two numbers?
    Last edited by icecube; November 30th 2009 at 09:29 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Quote Originally Posted by icecube View Post
    Thank you. I am confused though. Why do you wish to prove 1+2+2^2+...+2^k and 1+2+2^2+...+2^s are relatively prime?

    Also, why is it obvious that 2^d-1 is a factor of those two numbers?

    2^n-1 = (2^d-1)(1+2^d+2^{2d}+...+2^{(k-1)d})
    2^m-1 = (2^d-1)(1+2^d+2^{2d}+...+2^{(s-1)d})

    So gcd(2^n-1,2^m-1) = (2^d-1).gcd((1+2^d+2^{2d}+...+2^{(k-1)d}),(1+2^d+2^{2d}+...+2^{(s-1)d}))

    So if you show gcd((1+2^d+2^{2d}+...+2^{(k-1)d}),(1+2^d+2^{2d}+...+2^{(s-1)d}))=1 under the condition that (s,k)=1 we will be done. So can you do that? (You can infact replace 2 with any prime power, p^n)
    Last edited by aman_cc; November 30th 2009 at 10:29 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Oct 2009
    Posts
    12
    I see, I see! I forgot about that.
    I should be able to prove that though it's late so I'll try later tomorrow or this week. Thanks a lot.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Quote Originally Posted by Shanks View Post
    let d=gcd(n,m), then there exist positive integers k,s, such that n=kd,m=sd,(k,s)=1.
    Obviously, 2^d-1 is a common divisor of the two number.
    And, it is easy to prove that 1+2+2^2+...+2^k and 1+2+2^2+...+2^s are relatively prime if (k,s)=1.
    thus the result is proved!

    Shanks I think there is an errata in your post. Powers should be (k-1) and (s-1). As a counterexample to your claim consider k=5 and s=7
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member Shanks's Avatar
    Joined
    Nov 2009
    From
    BeiJing
    Posts
    374
    Yeah, I made a careless mistake.I forgot to the common divisor d and the k-1 things,.
    what I mean is the quotient of the number when divided by 2^d-1, but I write down the wrong representation.
    Thank you for your reminding me.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Quote Originally Posted by Shanks View Post
    Yeah, I made a careless mistake.I forgot to the common divisor d and the k-1 things,.
    what I mean is the quotient of the number when divided by 2^d-1, but I write down the wrong representation.
    Thank you for your reminding me.
    Yep that's exactly the approach I followed. Thanks (Enjoyed this question!)
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Oct 2009
    Posts
    95
    Quote Originally Posted by aman_cc View Post
    2^n-1 = (2^d-1)(1+2^d+2^{2d}+...+2^{(k-1)d})
    2^m-1 = (2^d-1)(1+2^d+2^{2d}+...+2^{(s-1)d})

    So gcd(2^n-1,2^m-1) = (2^d-1).gcd((1+2^d+2^{2d}+...+2^{(k-1)d}),(1+2^d+2^{2d}+...+2^{(s-1)d}))

    So if you show gcd((1+2^d+2^{2d}+...+2^{(k-1)d}),(1+2^d+2^{2d}+...+2^{(s-1)d}))=1 under the condition that (s,k)=1 we will be done. So can you do that? (You can infact replace 2 with any prime power, p^n)

    Exactly,

    Once you get to this part you can proceed as follows.

    It suffices to show that there exist two numbers x,y such that  x \left( \sum _{i=0} ^ {k-1} 2^{id} \right) - y \left( \sum _{i=0} ^ {s-1} 2^{id} \right) = 1.

    First, notice that

    \left( \sum _{j=0} ^ {r-1} 2^{jsd} \right) \left( \sum _{i=0} ^ {s-1} 2^{id} \right) = \sum _{i=0} ^ {rs-1} 2^{id}


    So suppose that \gcd(k,s)=1 then by definition there are positive numbers q,r such that q k - r s = 1.

    It is easy to verify that x= \sum _{j=0} ^ {q-1} 2^{jkd}

    and

    y= 2^{d}\left(\sum _{j=0} ^ {r-1} 2^{jkd} \right)

    satisfies the equation above, proving the result.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Oct 2009
    Posts
    12
    Thank you. However, \left( \sum _{j=0} ^ {r-1} 2^{jkd} \right) \left( \sum _{i=0} ^ {s-1} 2^{id} \right) = \sum _{i=0} ^ {rs-1} 2^{id} is clear to me but my professor would like us to make a complete proof, so I would have to prove this @_@. How would one go about proving this as well?
    I'm currently working on it as well though I'm stuck.

    -Several hours later-
    Still no closer to proving this.
    Last edited by icecube; December 5th 2009 at 04:31 PM.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Member
    Joined
    Oct 2009
    Posts
    95
    <br /> <br />
\sum _ {i=0} ^{rs-1} 2^{id} = 2^0 + ... + 2^{s-1} + 2^{s} + ... + 2^{2s-1} + 2^{2s} + ... + 2^{3s-1} + ... + 2^{(r-1)s} + ... + 2^{rs-1}<br />

    <br />
= 2^{0s} \sum _ {i=0} ^ {s-1} 2^i + 2^{s}  \sum _ {i=0} ^ {s-1} 2^i + ... + 2^{(r-1)s}  \sum _ {i=0} ^ {s-1} 2^i =  \left( \sum _ {i=0} ^ {s-1} 2^i \right) \left( \sum _{i=0} ^ {r-1} 2^{i s d}\right)<br />
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Newbie
    Joined
    Oct 2009
    Posts
    12
    O_O thank you. I'm just curious. Was this something you knew previously or did you just derive this relationship yourself? =O
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof involving functions.
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: September 8th 2011, 02:11 PM
  2. Proof involving GCD
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: October 11th 2010, 03:15 PM
  3. Proof involving e
    Posted in the Calculus Forum
    Replies: 1
    Last Post: March 2nd 2010, 03:44 PM
  4. Proof involving sets
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 19th 2008, 12:00 PM
  5. Proof involving primes
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 14th 2008, 09:01 AM

Search Tags


/mathhelpforum @mathhelpforum