One of $2^1-1,2^2-1,...,2^n-1$ is divisible by $n$ for odd $n$

Question

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.

Answer 1

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$

Answer 2

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\,$ }$$

Answer 3

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.