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