This question already has an answer here:

How do I do this question using the pigeonhole principle? Of course, I could just list down values of $k$ such that $2^k-1$ is divisible by 11. For example $k = 10$ would nicely solve the question but it requires listing and when the divisor gets bigger (For example show that there exists a $k$ where $2^k-1$ is divisible by 21, it's harder and much more complicated to solve it.

Are there any hints how I can use pigeonhole principle to solve this question?


marked as duplicate by Juniven, Scientifica, kingW3, zhoraster, Arnaud D. Mar 18 '17 at 19:54

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.

  • 2
    $\begingroup$ Not by using the pigeonhole principle, but still relevant: Fermat's Little Theorem. $\endgroup$ – Scientifica Mar 18 '17 at 12:42
  • 1
    $\begingroup$ It require listing? What about the Fermat's Little Theorem? Since $gcd(2,11)=1$, then $2^{10}\equiv 1\mod 11$ $\endgroup$ – Juniven Mar 18 '17 at 12:43
  • $\begingroup$ @Scientifica Thanks! I'll look into it!! $\endgroup$ – Icycarus Mar 18 '17 at 12:43
  • $\begingroup$ You're welcome :) $\endgroup$ – Scientifica Mar 18 '17 at 12:43
  • $\begingroup$ @ΘΣΦGenSan What if I don't list it? Then how would I know there exists a $k$ such that $2^k-1$ is divisible by 11? $\endgroup$ – Icycarus Mar 18 '17 at 12:46

Looking at the (potentially infinte) list of values $2^n$ modulo $11$, there must be distinct $m,n$ such that $2^m=2^n\mod 11$, by pigeon-hole. Without loss of generality, $m<n$, and then $2^{n-m}=1\mod 11$.


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