# Thread: Problem (solvable with the P.H.P.)

1. ## 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?

2. 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$.

3. Originally Posted by PaulRS
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.

4. Originally Posted by seven.j
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.