Results 1 to 3 of 3

Math Help - divisibility proof

  1. #1
    Member
    Joined
    Nov 2009
    Posts
    80

    divisibility proof

    Prove that if k and n are positive integers and k divides n, then 2^k-1 divides 2^n-1.

    I feel like I've done this problem before, but I'm not sure how to approach it.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by jmedsy View Post
    Prove that if k and n are positive integers and k divides n, then 2^k-1 divides 2^n-1.

    I feel like I've done this problem before, but I'm not sure how to approach it.
    Since k divides n, n = kl for some positive integer l.

    Use the fact that x-1 divides x^m - 1 for any positive integer m

    Choose x = 2^k and m = l in the above statement to get your answer.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Nov 2009
    Posts
    80
    Quote Originally Posted by Isomorphism View Post
    Since k divides n, n = kl for some positive integer l.

    Use the fact that x-1 divides x^m - 1 for any positive integer m

    Choose x = 2^k and m = l in the above statement to get your answer.
    I understand, thanks.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. divisibility proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 13th 2010, 12:05 PM
  2. Divisibility Proof
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: February 19th 2010, 02:01 AM
  3. Proof of divisibility
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: October 2nd 2008, 11:34 AM
  4. Divisibility proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 10th 2008, 08:07 AM
  5. divisibility proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 2nd 2007, 11:39 AM

Search Tags


/mathhelpforum @mathhelpforum