5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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]$ $\endgroup$ – Asimov Nov 10 '14 at 20:18
  • $\begingroup$ 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. $\endgroup$ – Asimov Nov 10 '14 at 20:20
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Simple and elegant. $\endgroup$ – Simon S Nov 10 '14 at 21:04
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.