Proving something using Pigeonhole Principle

Question

How do I prove the following using the Pigeonhole principle?

Let $n$ be an odd integer. Prove that there exists a positive integer $k$ such that $2^k \mod n = 1$.

I don't understand how I can prove this. Any help would be appreciated.

Answer 1

We know that $2^k\pmod n$ can only take a finite number of different values ($n-1$ to be precise, because $0$ is not possible). Since $k\in \mathbb N$ and $\mathbb N$ is infinite, there must be some value $r$ such that there are $m,n\in\mathbb N$ ($m\neq n$) for which $2^m\equiv 2^n\equiv r\mod n$. Now, suppose $m>n$ and say that $m=n+a$. Then, we get $2^{n+a}\equiv 2^n\mod n$. Since $\gcd(2,n)=1$, we may divide both sides by $2^n$, to get $$ 2^a\equiv 1\mod n $$ Thus, we can always (for any odd $n$) find a number $k$ such that $2^k\equiv 1\mod n$.