If n is an odd integer, show there exists a positive integer k such that 2^k mod n = 1. Hi I've been trying to solve this problem for at least 4 hours now but I can't figure it out. If anyone can help I would really appreciate it!
I am asked to prove this using the pigeonhole principle:
"If n is an odd integer, show there exists a positive integer k such that 2^k mod n = 1."
I know that n has n possible remainders (0,1,2,...,n-1) and that this may be the "pigeonholes". I also found that as you increase k in 2^k and calculate 2^k mod n, the remainders occur in a pattern... (Like for 2^k mod 5, when k=0 -> remainder is 2, k=1 -> r=4, k=2 -> r=3, k=3 -> r=1, then the pattern repeats 2,4,3,1.)
Also, I found n divides 2^k - 1, so 2^k - 1 = nb, for an integer b. Since 2^k is even and n is odd, b must be odd too...
(Thank you to both who helped me!!! I am really grateful :) )
 A: Hint:
Suppose that there are two integers $m$ and $m+k$ such that
$$
2^{m} = 2^{m+k} = 2^m \cdot 2^k \pmod{n}
$$
What can we say about $2^k$?

Solution:
I've tried to use your notation to make this more comprehensible. Let me know if anything is unclear.
We look at the first $n+1$ values of $\left(2^k \mod n\right)$.  We note by the pigeon-hole principle that since there are $n$ possible values modulo $n$, at least two of these have to be the same.  So, there are some integers $p>q$ for which
$$
2^p \mod n = 2^q \mod n
$$
Which I denote by
$$
2^p \equiv 2^q \pmod n
$$
We also note that
$$
2^{p-q}\cdot 2^q \equiv 2^{(p-q) + q} \equiv 2^{p} \pmod n
$$
So that we now have
$$
2^{p-q}\cdot 2^q  \equiv 2^q \pmod n
$$
By the Euclidean algorithm and since $2^{q}$ is relatively prime to $n$, we can find an $x$ and $y$ such that $x2^{q} + ny = 1 \implies x2^{q} = 1 - ny$.  As a consequence, we conclude that $x \cdot 2^{q} \pmod n = 1$.  We now multiply both sides of the above equivalence to get
$$
2^{p-q}\cdot \left(2^q\cdot x\right)  \equiv 2^q \cdot x \pmod n \implies\\
2^{p-q}\cdot 1  \equiv 1 \pmod n \implies\\
2^{p-q} \equiv 1 \pmod n
$$
So, we have $2^{p-q} \mod n = 1$ as desired.
A: Suppose not, in that case there are two integers $p>q\in{0... n-1}$ such that $2^{p}= 2^{q} \ Mod(n)$. Since $gcd(2^{q},n)=1$ Hence you can divide both sides by $2^q$ to obtain 
$2^{p-q}= 1 \ Mod(n)$

