Consider , we have integers, now consider the remainders when dividing by .
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?
Look at Paul's great hint. Each number gives a remainder between and upon division by . Since there are numbers it means there are so that and have the same remainder. Now since they have the same remainder it means . Now factor, . Because is odd it means and therefore . Set and there is your answer.