# Prove that there exists a $k$ such that $2^k-1$ is divisible by 11 [duplicate]

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

• It require listing? What about the Fermat's Little Theorem? Since $gcd(2,11)=1$, then $2^{10}\equiv 1\mod 11$ – Juniven Mar 18 '17 at 12:43
• @ΘΣΦ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? – 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$.