# 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.

• first personal feeling is to use the factoring of Mersenne numbers that are not prime. $2^p − 1 = 2 ^{ab} − 1 = (2^a)^b − 1 = (2^a − 1)[(2^a)^{b − 1} + (2^a)^{b − 2} + … + 2^a + 1]$ – Asimov Nov 10 '14 at 20:18
• If n is not prime, you get this factoring. Perhaps there is a way to show that some n makes a factoring that includes any odd number. – Asimov Nov 10 '14 at 20:20

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$.

• Simple and elegant. – Simon S Nov 10 '14 at 21:04

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.

$$(2k+1) \mid 2^{\phi(2k+1)} -1$$ by http://en.wikipedia.org/wiki/Euler%27s_theorem

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$.