Timeline for Number of cycles under a certain action on Z/nZ

3 events

when toggle format	what		by	license	comment
Sep 28, 2019 at 0:15	comment	added	Padraig Ó Catháin		Deciding whether all non-zero elements of $\mathbb{Z}/p\mathbb{Z}$ are in the same orbit under multiplication by $k$ is the same as deciding whether $k$ is a primitive root in the field. Such elements are easy to find computationally, but no characterisation of such elements is known. (E.g. it is not known for which primes $2$ is a primitive root.) Since we can't work out even the cycle structure in general, I don't think there's an efficient way to compute canonical representatives for each cycle.
Sep 27, 2019 at 18:31	comment	added	Rory		Thanks, this is exactly it! Is there some closed-form mathematical description of the order of $[k]$ in $U_n$? The second q is... Suppose I consider the elements of $\mathbb{Z}/n\mathbb{Z}$ in turn. And suppose I maintain a "visited" bit for each. $0$ is solo, $1$ leads through a cycle of $5$, the same with $2$. Now, as I consider $3, 4, 5, ...$ I'll see that I've flipped the "visited" bit for each element. This saves recomputing any cycle, but it comes at the cost of maintaining bits. Can I instead map each element to a canonical element of its cycle in such a way to avoid BOTH costs?
Sep 27, 2019 at 12:24	history	answered	Geoff Robinson	CC BY-SA 4.0