, 2018

For an arbitrary positive integer $m$, not divisible by $3$, consider the permutation $x\mapsto 3x\pmod{m}$ on the set $\{1,2,\ldots,m-1\}$. This permutation can be decomposed into disjoint cycles; for instance, for $m=10$ the cycles are $(1\mapsto3\mapsto9\mapsto7\mapsto1)$, $(2\mapsto6\mapsto8\mapsto4\mapsto2)$ and $(5\mapsto5)$. For which integers $m$ is the number of cycles odd?