0

Hypothesis: $\forall$ odd $n > 1$, $\exists\ m <n$ such that $2^m = 1\mod n$.

This seems to hold for small values. For example: For $n=5$, $m=4$ satisfies as $2^4 = 16 = 1\mod5$. For $n=65$, $m=12$ satisfies as $2^{12} = 4096 = 1\mod 65$.

Is there a straightforward (dis)proof of the above hypothesis?

Can $m$ be more tightly constrained? Is there a 'formula' mapping $n$ to $m$?

aSteve
  • 147
  • 2
    Take $m = \varphi(n)$, where $\varphi$ is Euler's totient function. That's in general not the smallest exponent, but it always works. – Daniel Fischer Jul 02 '13 at 20:48
  • Question to determine how an answer should look like: Have you any background in algebra, do you know what a group is, what an exponent of a group is? – Daniel Fischer Jul 02 '13 at 20:53

1 Answers1

2

A more or less direct proof would be to note that $2,2^2,2^3,\dots, 2^n$ yields $n$ numbers not divisible by $n$, so two of them must be congruent, modulo $n$. That would mean that $2^{i}-2^j$ must be divisible by $n$ for some $i,j\in\{1,2,\dots,n\}$. Since $n$ is odd, this means that $2^{i-j}-1$ is divisible by $n$ (if $i>j$.)

As Daniel Fischer pointed out, there is a function $\phi(n)$ for which $2^{\phi(n)}=1\pmod n$ for all odd $n$. It is called "the Euler totient function." Proving that this is true for all odd $n$ is a little more work than my simple argument here.

In general, the smallest such $m$ is called the order of $2$ modulo $n$.

Thomas Andrews
  • 177,126
  • I love the simplicity of that proof. Thanks, too, for the pointers to Euler's Totient - which looks perfectly relevant... something I'll need to read/consider in more detail. – aSteve Jul 02 '13 at 21:30