Consider the rings $\mathbb{Z} /n \mathbb{Z}$ where $n$ is odd. Every number is even in such rings. Assume we start with $1$ and keep "halving" until we get back to $1$. What can be said about the number of times we can halve one in relation to $n$? Some examples:

$\mathop\bmod 7$: $1 = 4+4$, $4 = 2+2$, $2 = 1+1$

We can halve one three times $\mathop\bmod 7$.

$\mathop\bmod 11$: $1 = 6+6$, $6 = 3+3$, $3 = 7+7$, $7 = 9+9$, $9 = 10+10$, $10 = 5+5$, $5 = 8+8$, $8 = 4+4$, $4 = 2+2$, $2 = 1+1$

We can halve one ten times $\mathop\bmod 11$.

For what $n$ can we halve one $n-1$ times?


1 Answer 1


The question is very difficult. We give a brief description of what is known.

If $n$ is not a prime, then we cannot "divide by $2$" $n-1$ times. In more conventional language, if $n$ is not prime, then the order of $2$ modulo $n$ is not equal to $n-1$/

If $n$ is prime, it is possible for the order of $2$ to be $n-1$, that is, for $2$ to be a generator of the multiplicative group, for $2$ to be a primitive root of $n$.

If the prime $n$ is of the form $8k\pm 1$, then $2$ cannot be a primitive root of $n$. However, little is known for primes of the form $8k\pm 3$. It is not even known whether there are infinitely many primes that have $2$ as a primitive root, though there is overwhelming numerical evidence that there are.

Note that your computation showed that $2$ is not a primitive root of $7$ (this can be also shown without computation, since $7$ is of the form $8k-1$). You also showed that $2$ is a primitive root of $11$.

More generally, even for prime $n$, not a great deal can be said about the order of $2$ modulo $n$, that is, the number of divisions until we get to $1$. It is easy fact that the order must divide $n-1$. For non-primes $n$, we can say that the order of $2$ divides $\varphi(n)$, where $\varphi$ is the Euler $\varphi$-function. This can be replaced by the Carmichael function $\lambda$.

Your problem can be expressed equivalently as a question about the cycle length of the binary expansion of $\frac{1}{n}$, where $n$ is odd.

  • $\begingroup$ Thanks. Obviously, the minimum is when $n=2^k-1$ and the order of 2 is $k$. If $n$ is prime then $k$ divides $n-1$. Could this be used to find large primes? $\endgroup$ Dec 7, 2013 at 22:27
  • $\begingroup$ Well, Mersenne primes have almost always been the largest explicitly known primes. $\endgroup$ Dec 8, 2013 at 1:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .