One of $2^1-1,2^2-1,...,2^n-1$ is divisible by $n$ for odd $n$ 
Let $n$ be an odd integer greater than 1. Show that one of the numbers $2^1-1,2^2-1,...,2^n-1$ is divisible by $n$.

I know that pigeonhole principle would be helpful, but how should I apply it? Thanks.
 A: Observe that there are $n$ such number with the possible number of remainders is $n-1$ from $1,2,\cdots,n-2,n-1$ because  if $0$  is a remainder for some $r,$ then $n|(2^r-1)$ and we are done.
Otherwise using Pigeonhole Principle, at least for two distinct values $r$ we shall have same remainder
Let $2^t-1\equiv2^s-1\pmod n$ where $t>s$
$\implies n|\{(2^t-1)-(2^s-1)\}\implies n| 2^s(2^{t-s}-1)\implies n|(2^{t-s}-1)$ as $(2,n)=1$
Clearly, $0<t-s<n$ as $n\ge t>s\ge1$
A: Hints:
$$(1)\;\;\;2^k-1=2^{k-1}+2^{k-2}+\ldots+2+1\;,\;\;k\in\Bbb N$$
$$(2)\;\;\;\text{Every natural number $\,n\,$ can be uniquely written in base two }$$
$$\text{with maximal power of two less than $\,n\,$ }$$
A: Hint: We know that $\gcd(2,n)=1$
$2^{\phi(n)} \equiv 1\pmod n$
And $1<\phi(n)<n$ and we already have $2^1-1 \equiv 1 \pmod n$
You can use pigeon-hole principle after this.
Another Approach: 
Actually, the $\phi(n)$ or $\lambda(n)$ occurs just between $1$ and $n$, therefore,
$2^{\lambda(n)} \equiv 1 \pmod n  \implies 2^{\lambda(n)} -1 \equiv 0 \pmod n$.
This involves no Pigeons or Pigeon-holes.:)
Here $\lambda(n)$ is smallest number which occurs before $\phi(n)$ such that $a^{\lambda(n)} \equiv 1 \pmod n$. Also known as Carmichael Number.
