# pigeonhole principle divisibility proof

Let $n$ be some positive odd number. Prove, in terms of the pigeonhole principle, that there exists some positive integer $k$ such that $n\mid 2^k-1$.

• Recall $\text{n } | \text{ } 2^{k - 1}$ is the same as $2^{k-1} \equiv 0 \mod \text{n}$. Is there any theorem you know for that is similar to this? – David Nov 7 '13 at 2:32

We use congruence notation. Consider the remainders when $2^1,2^2,2^3,\dots,2^n$ is divided by $n$. These remainders can take no values other than $1,2,3,\dots,n-1$.
The list $2^1,2^2,\dots, 2^n$ has $n$ numbers, and there are at most $n-1$ possible remainders. It follows that there exist integers $a$ and $b$, with $1\le a\lt b\le n$ such that $2^a\equiv 2^b\pmod{n}$. Thus $2^{b-a}\equiv 1\pmod{n}$.
• IMHO, it should be mentioned that $0$ is not a possible remainder (because $n$ is odd) and that the last argument is a consequence of Gauss theorem. – Adren Jul 10 '18 at 16:46
• Another version of the same result is as follows : if $n$ is an odd positive integer, then the binary representation of some multiple of $n$ contains only ones. – Adren Jul 10 '18 at 16:52