Number of cycles of doubling map mod n

Question

Playing with some rhythm ideas, I stumbled on the sequence A000374. It claims that the number of cycles of $f(x) = 2x \bmod n$ is the same as the number of distinct irreducible factors of $x^n - 1 \bmod 2$ (and furthermore that the degrees of the factors correspond to the lengths of the cycles), but no proof is given, and I can't see how the linked paper relates. This is a fascinating result to me. How does it work?

Answer 1

This is far from being a complete answer but may be useful in illustrating the relationship. For an immediate simplification, suppose $n$ to be an odd prime.

Let $Q$ be the order of $2$ modulo $n$. Then the cycles of $f$ are $(0)$ and $\frac{n-1}{Q}$ cycles of length $Q$, one of which is $(1,2,4, ...,2^{Q-1}).$

The irreducible factors are less easy to deal with. However, consider an irreducible factor of $x^n-1$ mod $2$. Over a splitting field let its roots be $\{w^t\}$ where $t\in S=\{a,b,c,...\}$.

Then we know that, for example, $w^a+w^b+w^c+...$ is either $0$ or $1$. Then squaring gives the same value for $(w^a+w^b+w^c+...)^2=(w^2)^a+(w^2)^b+(w^2)^c+...$. Similarly we can look at $(w^aw^b+w^aw^c+...)^2$ and so on.

We can conclude that our irreducible factor also has roots $\{w^{2t}\}$ where $t\in S$. In other words multiplying by $2$ simply permutes the elements of $S$.

$S$ therefore consists of cycles of $f$. Of course, it remains to prove that $S$ is precisely one cycle.