$2^n$ modulo n where n is odd always yields either an even or $1$

Question

I'm attempting to do a pidgeonhole proof to prove that for some odd integer n, there is always a $2^k$ such that $2^k \mod(n) = 1$. I know that $2^n \mod(n)$ will always yield either an even number or $1$, but I don't know how to prove why that is. I know the answer is obvious and staring me in the face, but if anyone could provide some assistance, it would be much appreciated.

Answer 1

If you know basic group theory it is easy: since $n$ is odd the map $\,x\mapsto 2x\pmod n\,$ is $1$-$1$ so onto, i.e. a permutation. Thus $(1\ 2\ 4\ 8 \ldots) = $ orbit of $\,1\,$ is a cycle of the permutation. Such cycles are purely periodic (i.e. no preperiodic part). Hence $\,2^n = 1\,$ for $\,n$ = length of the orbit (cycle) of $\,1$.

Remark $\ $ The cyclic nature of permutation orbits is often inadvertantly reinvented, something that I call "reinventing the wheel (cycle)". Here are some less trivial examples.

Answer 2

Consider the set $S=\{1,2,\ldots,2^n\}$. It has $n+1$ elements. Can the least non-negative residues $$1\bmod n,\; 2\bmod n,\;\ldots\; 2^n\bmod n$$ all be distinct? If we had $2^i\equiv 2^j\bmod n$ for some $i\neq j$, can you turn that into a statement that $2^k\equiv 1\bmod n$ for some $k\neq 0$ ? (hint: here is where you need $n$ to be odd)

P.S. If you were allowed methods other than the pigeonhole principle, I think it would be easier to prove that $2^k\equiv 1\bmod n$ for some $k$ by simply using Euler's theorem (Wikipedia), since $n$ odd implies $\gcd(2,n)=1$ and thus $2^{\varphi(n)}\equiv 1\bmod n$ where $\varphi$ is Euler's phi function.