# 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 $2^0,2^1,2^2,2^{m-1},2^{m}$, we have $m+1$ integers, now consider the remainders when dividing by $m$.

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

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