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 🙂 )
Best Answer
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.