Let $n\geq 2$ be an integer and consider the action $\Phi: \mathbb{Z}_n^{*}\times \mathbb{Z}_n \rightarrow \mathbb{Z}_n$ defined as $$\Phi(\alpha)(x)=(\alpha x \textrm{ mod } n),$$ i. e. simply the action of automorphisms acting on the group $\mathbb{Z}_n$.
(Notation: $\mathbb{Z}_n$ denotes the usual additive group with addition modulo $n$, $\mathbb{Z}_n^{*}$ the set of numbers between $1$ and $n-1$ coprime to $n$ with multiplication modulo $n$.)
My question is: How do the orbits of $\Phi$ look like?
It is easily seen (for instance, from the description of the action as action of automorphism group acting on its group) that whenever $\Phi(\alpha)(x)=y$ for some $\alpha \in \mathbb{Z}_n^{*}$, then $\gcd(x,n)=\gcd(y,n)$, i.e. the elements $x$ and $y$ generate the same subgroup. Does the converse hold as well, i. e. are the orbits simply sets of all generators of some subroup of $\mathbb{Z}_n$? Or are they "finer" in general?
(If I didn't write the code somewhat horribly wrong, I verified this for $n=2, \dots, 1000,$ so I'm inclined to believe it is actually true.)
My attempt so far:
The claim is well known for generators of the group $\mathbb{Z}_n$. Take $d \mid n$. Then a natural way how to describe the subgroup of order $d$ is as $k\mathbb{Z}_d$, where $kd=n$. Now the group $\mathbb{Z}_d$ has its own group of automorphism $\mathbb{Z}_d^{*}$ acting on $\mathbb{Z}_d$ as follows: $$\Psi'(\beta)(x)=(\beta x \textrm{ mod } d),$$ and it is not difficult to check that the action is "translated" to the notation of the group $k\mathbb{Z}_d$ as $$\Psi(\beta)(kx)=(\beta kx \textrm{ mod } n).$$ IMO, the difficulty lies in relating these maps (i.e. those corresponding to numbers coprime to $d$) to the maps given by the action $\Phi$ (i.e. those corresponding to numbers coprime to $n$). On one hand, not every number coprime to $d$ needs to be coprime to $n$ (but the converse is true), on the other hand, the numbers comprime to $n$ are taken from larger interval.
After reading a hint in comments (which mysteriously disappeared afterwards) I was able to come up with this:
First assume that $n=p^m,$ where $p$ is a prime. Then, for the chosen subgroup $k\mathbb{Z}_d$ of $\mathbb{Z}_n$, consider the action $\Psi$ as described in the original post. Clearly any two generators $kl_1, kl_2$ of $k\mathbb{Z}_d$ are in the same orbit of $\Psi$ - that is, there exists $1 \leq \beta \leq d-1$ coprime to $d$ such that $\beta kl_1\equiv kl_2\text{ (mod }n)$. But then, since $n=p^m$ and therefore $d=p^r$ for $r \leq m$, $\beta$ is coprime to $n$ as well, hence contained in $\mathbb{Z}_n^{*}$.
Now the general case: Let $n=p_1^{m_1}p_2^{m_2}\dots p_s^{m_s}$. Then by CRT, there is a ring isomorphism $$\varphi:\mathbb{Z}_n \rightarrow \prod_{i=1}^{s}\mathbb{Z}_{p_i^{m_i}}, \;\; \varphi: l \mapsto (l \textrm{ mod } p_1^{m_1}, l \textrm{ mod } p_2^{m_2}, \dots l \textrm{ mod } p_s^{m_s} ),$$
which induces the isomorphism of the groups of units $\psi:\mathbb{Z}_n^{*} \rightarrow \prod_{i=1}^{s}\mathbb{Z}_{p_i^{m_i}}^{*}$. Take two elements $l_1,l_2$ of the same order in $\mathbb{Z}_n$. Then the images of the elements "have the same order component-wise", i.e. for every $i$, $l_j \textrm{ mod } p_i^{m_i}, j=1,2$ have the same order in $\mathbb{Z}_{p_i^{m_i}}$. That is, there exist $\beta_i, i=1, \dots, s$, $\beta_i$ coprime to $p_i$, such that $\beta_i l_1\equiv l_2 \text{ (mod }p_i^{m_i})$. Then by the isomorphism $\psi,$ there exists a unique $\alpha\in \mathbb{Z}_n^{*}$ such that $\psi(\alpha)=(\beta_1,\dots,\beta_s) $. Such $\alpha$ then clearly takes the element $l_1$ to $l_2$.