Results 1 to 4 of 4

Math Help - Problem (solvable with the P.H.P.)

  1. #1
    Newbie
    Joined
    Oct 2008
    Posts
    8

    Problem (solvable with the P.H.P.)

    Hi everyone, I have this problem here that I'm struggling with:

    Let m be an odd integer. Prove that there exists a positive integer n such that (2^n)-1 is a multiple of m.

    My teacher said this is solvable using the pigeon hole principle, but I can't see the solution.

    Hints?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Consider 2^0,2^1,2^2,2^{m-1},2^{m}, we have m+1 integers, now consider the remainders when dividing by m.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2008
    Posts
    8
    Quote Originally Posted by PaulRS View Post
    Consider 2^0,2^1,2^2,2^{m-1},2^{m}, we have m+1 integers, now consider the remainders when dividing by m.
    hmm, at first it looked good, but now that I think about it, this assumes that n can't be greater than m. also, while there are m remainders, why can't all the remainders be the same? there is no proof that the remainder 0 will be hit.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by seven.j View Post
    hmm, at first it looked good, but now that I think about it, this assumes that n can't be greater than m. also, while there are m remainders, why can't all the remainders be the same? there is no proof that the remainder 0 will be hit.
    Look at Paul's great hint. Each number 2^0,...,2^m gives a remainder between 0 and m upon division by m. Since there are m+1 numbers it means there are m\geq m_2 > m_1 \geq 0 so that 2^{m_2} and 2^{m_1} have the same remainder. Now since they have the same remainder it means m| ( 2^{m_2} - 2^{m_1}). Now factor, m | 2^{m_1} (2^{m_2 - m_1} - 1). Because m is odd it means \gcd(m,2^{m_1}) = 1 and therefore m|(2^{m_2 - m_1} - 1). Set n=m_2 - m_1 and there is your answer.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Is this congruence solvable?
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: July 20th 2011, 09:42 PM
  2. S4 solvable
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: May 5th 2011, 10:46 PM
  3. Solvable Group
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: April 12th 2010, 12:14 PM
  4. solvable?
    Posted in the Business Math Forum
    Replies: 7
    Last Post: November 5th 2009, 07:54 PM
  5. Is this solvable?
    Posted in the Algebra Forum
    Replies: 0
    Last Post: March 11th 2009, 09:00 PM

Search Tags


/mathhelpforum @mathhelpforum