Proving any odd number is a factor of $2^n -1$ for some $n$ I'm struggling with a proof of the following. I feel like it should be a one-liner or something simple but I'm just not grasping the idea:
Suppose that m is an odd natural number. Prove that there is a natural number $n$ such that $m$ divides $2^n -1$
Any help would be much appreciated, thanks.
 A: A start: Consider the remainders when $2$, $2^2$, $2^3$, $2^4$, and so on are divided by $m$.  
By the Pigeonhole Principle there exist distinct positive integers $i\lt j$ such that $2^i$ and $2^j$ have the same remainder on division by $m$.
Show that $m$ divides $2^{j-i}-1$.
A: $$(2k+1) \mid 2^{\phi(2k+1)} -1 $$ 
by http://en.wikipedia.org/wiki/Euler%27s_theorem
A: You want to find $n$ such that
$$2^n\equiv1\mod m$$
It's clear that the values of $2^n\text{ mod } n$ start repeating after a while. Can it happen that $1$ is excluded from the cycle? No because $2$ has an inverse $\text{mod }m$, namely $(m+1)/2$, so you can go in reverse and must reach $1$ eventually.
A: Let 
$$m=\prod_{k=1}^r p_k^{\alpha_k},\qquad p_k\ne2$$
the primary decomposition of $m$ and since $\gcd(2,p_k^{\alpha_k})=1$ then $\overline 2$ is invertible in $\Bbb Z_{p_k^{\alpha_k}}$ so there's $\mu_k\in\Bbb N$ such that
$$2^{\mu_k}\equiv 1\pmod {p_k^{\alpha_k}}$$
Now we conclude using The chinese remainder theorem and we take $n=\sum\limits_{k=1}^r \mu_k$.
A: RTP: for every odd +ve integer, m, there exists n such that m|$2^n-1$
Consider a of numbers A = {$2^0-1$, $2^1-1$, $2^2-1$, $2^3-1$, ... , $2^m-1$ ... }
Let $x$ be an element of A such:
$x$ = $2^i-1$
where $i$ is an integer contained in [$0$, $m+1$]
$x$ = $r$ (Mod $m$)   such $r$ is contained in  [$0$, $m$)
Note there are $m+1$ number of possible $x$ values and only $m$ possible values for $r$ thus by the pigeonhole principle there must be at least two values of x with the same remainder $r$.
Let $2^a-1$ and $2^b-1$ be two such values such a cannot equal b and a greater than b say. [$a-b$ is some +ve integer]
$2^a-1$ = $2^b-1$ (mod $m$)
--> $m$ | $2^a-1$ - ($2^b-1$)
--> $m$ | $2^a-2^b$
--> $m$ | $2^b(2^a/2^b -1)$
but $m$ is an odd integer
--> $m$ |$2^a/2^b - 1$
--> $m$ |$2^n -1$     where $n$ is some +ve integer as required
