0
$\begingroup$

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.

$\endgroup$

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ 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}$? $\endgroup$ – Steven Stadnicki Feb 15 '14 at 0:54
  • $\begingroup$ I'm pretty sure this has been asked (and answered) very recently. And it was marked as homework in the first post math.stackexchange.com/questions/674303/… $\endgroup$ – TooTone Feb 15 '14 at 1:01
4
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – user126032 Feb 15 '14 at 17:53
  • $\begingroup$ @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. $\endgroup$ – Ragnar Feb 15 '14 at 17:56
  • $\begingroup$ 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. $\endgroup$ – user126032 Feb 15 '14 at 18:03
  • $\begingroup$ @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$. $\endgroup$ – Ragnar Feb 15 '14 at 19:09

Not the answer you're looking for? Browse other questions tagged or ask your own question.