A pigeonhole problem from "Conjecture and Proof"

Question

I don't really know how to start this problem at all. I would like a solution or even hints.

"Prove that for every odd integer $n$ there is an integer $i$ such that $n \mid 2^i- 1.$"

The chapter in the book which provides this problem as an exercise is entitled "The Pigeonhole Principle" so I assume that the Pigeonhole Principle will be used in some way. The book is entitled "Conjecture and Proof" by Miklos Laczkovich.

Answer 1

Consider the numbers $2^1-1, 2^2-1,\dots$ Since there are infinitely many, at least two must have the same remainder modulo $n$. (This is the application of the pigeonhole principle. Naturally, you do not need to consider infinitely many of these numbers to reach the conclusion.)

Say that $i<j$, and that $2^i-1$ and $2^j-1$ have the same remainder modulo $n$. Then $n$ divides their difference, $2^j-2^i=2^i(2^{j-i}-1)$. Now use that $n$ is odd to conclude from this that, in fact, $n$ divides $2^{j-i}-1$.

Answer 2

HINT: Suppose that $i<k$ and $2^i\equiv 2^k\pmod n$. Then $n\mid 2^k-2^j=2^j(2^{k-j}-1)$. There are only $n$ congruence classes modulo $n$, and there are more than $n$ numbers of the form $2^k$ for $k\in\Bbb N$, so ...

Answer 3

Consider the set $\{2^k:k\in \Bbb N\}$. This set is infinite, so by the pigeonhole principle there are $l,m$ such that $l\lt m$ and $2^l, 2^m$ are in the same equivalence class of $\Bbb Z/n\Bbb Z$. Take $i=m-l$ then $2^i\equiv 1(\text{mod}\;n)$.