# Proving something using Pigeonhole Principle [duplicate]

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.

## marked as duplicate by Lost1, ncmathsadist, Daryl, Shuchang, user61527 Feb 15 '14 at 3:24

• Hint: how many different values can $2^k$ take $\mod n$? If we have $2^k\equiv a$ and also $2^j\equiv a$, what is $2^{k-j}$? – Steven Stadnicki Feb 15 '14 at 0:54
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$.
• Can you explain how you went from $2^m$ ≡ $2^n$ ≡ r mod n to $2^n+a$ ≡ $2^n$ mod n? I also don't understand why the gcd(2,n) = 1 is necessary – user126032 Feb 15 '14 at 17:53
• @user126032, we divide $2^{n+a}\equiv 2^n$ by $2^n$, which is possible because $\gcd(2^n,d)=1$. That results in $2^a\equiv 1$, which is what we want. – Ragnar Feb 15 '14 at 17:56
• how can we say 2^(n+a) ≡ $2^n$? Sorry, but my teacher did a very poor job of explaining the pigeonhole principle and its very confusing to me. – user126032 Feb 15 '14 at 18:03
• @user126032, there are only $n-1$ possible remainders for $2^k$. Since there are more than $n$ possible values for $k$, there must be $m\neq n$ such that $2^m\equiv 2^n\mod k$. – Ragnar Feb 15 '14 at 19:09