USSR MO 1980 pigeonhole-principle

Question

Let $n \geq 3$ be an odd number. Show that there is a number in the set $\{2^1-1,2^2-1,...,2^{n-1} - 1\}$ which is divisible by $n$.

Answer 1

For $1\le k \le n-1$, let $r_k$ be the remainder when $2^k$ is divided by $n$.

Since $n$ is odd, we have $r_k > 0$, for all $k$.

Then for all $k$, we have $r_k\in S=\{1,...,n-1\}$.

Consider $2$ cases, based on whether or not the $n-1$ values $r_1,...,r_{n-1}$ are all distinct.

Case (1):$\;$The $n-1$ values $r_1,...,r_{n-1}$ are all distinct.

Then since $S$ has exactly $n-1$ elements, it follows that $\{r_1,...,r_{n-1}\}=S$.

Hence $r_k=1$ for some $k$, so for that $k$ we have $n{\,\mid\,}2^k-1$.

Thus for case $(1)$, the claim holds.

Case (2):$\;$The $n-1$ values $r_1,...,r_{n-1}$ are not all distinct.

Then $r_i=r_j$ for some $i,j$ with $i < j$.

Thus, since $2^i$ and $2^j$ have the same remainder when divided by $n$, it follows that $2^j-2^i$ is a divisible by $n$. \begin{align*} \text{Then}\;\; &n{\,\mid\,}2^j-2^i\\[4pt] \implies\; &n{\,\mid\,}2^i(2^{j-i}-1)\\[4pt] \implies\; &n{\,\mid\,}2^{j-i}-1\qquad\text{[since $n$ is odd]}\\[4pt] \end{align*} hence $n{\,\mid\,}2^k-1$ where $k=j-i$.

Noting that $1\le j-i\le n-2$, it follows that for case $(2)$, the claim also holds.

This completes the proof.

Answer 2

By Euler’s Theorem , $a^{\phi(n)} \equiv {1}$ (mod $n), \ $ if $GCD(a,n)=1$. Taking $a=2$, $n$ is odd means the GCD condition is satisfied.

Since $1 \leqslant \phi(n) \leqslant n - 1$ , There exists one of the elements in the set that is divisible by n.