Results 1 to 4 of 4

Thread: 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 $\displaystyle 2^0,2^1,2^2,2^{m-1},2^{m}$, we have $\displaystyle m+1$ integers, now consider the remainders when dividing by $\displaystyle 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 $\displaystyle 2^0,2^1,2^2,2^{m-1},2^{m}$, we have $\displaystyle m+1$ integers, now consider the remainders when dividing by $\displaystyle 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
    10
    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 $\displaystyle 2^0,...,2^m$ gives a remainder between $\displaystyle 0$ and $\displaystyle m$ upon division by $\displaystyle m$. Since there are $\displaystyle m+1$ numbers it means there are $\displaystyle m\geq m_2 > m_1 \geq 0$ so that $\displaystyle 2^{m_2}$ and $\displaystyle 2^{m_1}$ have the same remainder. Now since they have the same remainder it means $\displaystyle m| ( 2^{m_2} - 2^{m_1})$. Now factor, $\displaystyle m | 2^{m_1} (2^{m_2 - m_1} - 1)$. Because $\displaystyle m$ is odd it means $\displaystyle \gcd(m,2^{m_1}) = 1$ and therefore $\displaystyle m|(2^{m_2 - m_1} - 1)$. Set $\displaystyle 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: Jul 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: Apr 12th 2010, 12:14 PM
  4. solvable?
    Posted in the Business Math Forum
    Replies: 7
    Last Post: Nov 5th 2009, 07:54 PM
  5. Is this solvable?
    Posted in the Algebra Forum
    Replies: 0
    Last Post: Mar 11th 2009, 09:00 PM

Search Tags


/mathhelpforum @mathhelpforum