# Orbits of $\mathbb{Z}/n\mathbb{Z}$ under the action of its multiplicative group $\left(\mathbb{Z}/n\mathbb{Z}\right)^{\times}$

Let $$\mathbb{Z}/n\mathbb{Z}$$, $$\left(\mathbb{Z}/n\mathbb{Z}\right)^{\times}$$, and $$\mathcal{D}_n$$ be the ring of integers modulo $$n$$, its multiplicative group of order $$\varphi(n)$$, and the set of divisors of $$n$$, respectively. The map $$\phi: \left(\mathbb{Z}/n\mathbb{Z}\right)^{\times}\times\mathbb{Z}/n\mathbb{Z}\rightarrow\mathbb{Z}/n\mathbb{Z}$$, given by $$\phi(g,x):=gx$$ is a left group action on $$\mathbb{Z}/n\mathbb{Z}$$. I am having a hard time in showing that $$\phi$$ decomposes $$\mathbb{Z}/n\mathbb{Z}$$ into $$|\mathcal{D}_n|$$-many distinct orbits given by $$\left(\mathbb{Z}/n\mathbb{Z}\right)^{\times}\cdot\bar{\delta}$$, where $$\delta$$ is a divisor of $$n$$. Let me give an example. If $$n=12$$, then $$\mathbb{Z}/12\mathbb{Z}=\{\bar{0},\dots,\bar{11}\}$$, $$\left(\mathbb{Z}/12\mathbb{Z}\right)^{\times}=\{\bar{1}, \bar{5},\bar{7}, \bar{11}\}$$, and $$\mathcal{D}_{12}=\{1,2,3,4,6,12\}$$ and we have: $$\left(\mathbb{Z}/12\mathbb{Z}\right)^{\times}\cdot\bar{1}=\{\bar{1}, \bar{5},\bar{7}, \bar{11}\},$$ $$\left(\mathbb{Z}/12\mathbb{Z}\right)^{\times}\cdot\bar{2}=\{\bar{2}, \bar{10}\},$$ $$\left(\mathbb{Z}/12\mathbb{Z}\right)^{\times}\cdot\bar{3}=\{\bar{3}, \bar{9}\},$$ $$\left(\mathbb{Z}/12\mathbb{Z}\right)^{\times}\cdot\bar{4}=\{\bar{4}, \bar{8}\},$$ $$\left(\mathbb{Z}/12\mathbb{Z}\right)^{\times}\cdot\bar{6}=\{\bar{6}\},$$ $$\left(\mathbb{Z}/12\mathbb{Z}\right)^{\times}\cdot\bar{0}=\{\bar{0}\},$$ and $$\bigcup_{\delta|12}\left(\mathbb{Z}/12\mathbb{Z}\right)^{\times}\cdot\bar{\delta}=\mathbb{Z}/12\mathbb{Z}.$$ I would be very grateful for any help or insights.

• crossposted : mathoverflow.net/questions/395022/… – verret Jun 10 at 18:36
• "... its multiplicative group of order $n$..." The multiplicative group is of order $\varphi(n)$ (Euler's phi), not $n$. – Arturo Magidin Jun 10 at 18:54
• @ArturoMagidin Yes, of course. Thank you. – L. Cardoso Jun 10 at 18:57

## 1 Answer

Let $$k\ge l$$ be two positive integers and let $$p$$ be a prime number, then all integers $$a\in\{1,\ldots,p^l-1\}$$ coprime to $$p^l$$ are clearly coprime to $$p^k$$ as well, so the homomorphism $$(\mathbb{Z}/p^k\mathbb{Z})^\times\to\left(\mathbb{Z}/p^l\mathbb{Z}\right)^\times$$ is surjective. Note that for all pairs of coprime positive integers $$m_1,m_2$$, we have $$\left(\mathbb{Z}/m_1m_2\mathbb{Z}\right)^\times\cong \left(\mathbb{Z}/m_1\mathbb{Z}\right)^\times\times\left(\mathbb{Z}/m_2\mathbb{Z}\right)^\times.$$ It follows that for all positive integers $$n$$ and $$d\mid n$$, the natural map $$\left(\mathbb{Z}/n\mathbb{Z}\right)^\times \to \left(\mathbb{Z}/d\mathbb{Z}\right)^\times$$ is surjective. In particular, the kernel has cardinality $$\varphi(n)/\varphi(d)$$.

Now let $$n$$ and $$d\mid n$$ be positive integers and let $$x\in \mathbb{Z}/n\mathbb{Z}$$ of order $$d$$. Consider the action of $$\left(\mathbb{Z}/n\mathbb{Z}\right)^\times$$ on $$\mathbb{Z}/n\mathbb{Z}$$ and in particular the stabilizer of $$x$$. This stabilizer may be identified with all elements $$g\in \{1,\ldots, n-1\}$$ coprime to $$n$$ such that $$gx=x$$, which may be rewritten as $$n\mid (g-1)x$$, or $$d\mid g-1$$. These $$g$$ make up precisely the kernel of the aforementioned homomorphism $$\left(\mathbb{Z}/n\mathbb{Z}\right)^\times\to\left(\mathbb{Z}/d\mathbb{Z}\right)^\times$$.

We conclude that the cardinality of the stabilizer is $$\varphi(n)/\varphi(d)$$, and with the orbit-stabilizer theorem it follows that the orbit of $$x$$ consists of precisely $$\frac{\varphi(n)}{\varphi(n)/\varphi(d)}=\varphi(d)$$ elements. Finally, note that automorphisms preserve order, so the orbit of $$x$$ can only contain elements of order $$d$$, and there exist precisely $$\varphi(d)$$ elements of order $$d$$ in $$\mathbb{Z}/n\mathbb{Z}$$. We are done.

• The relationship between $x$ and $d$ seems unclear to me; did you mean to choose $d$ to be the smallest integer with $dx \equiv 0 (mod n)$ (which is not hard to prove must be a divisor of $n$)? – user44191 Jun 10 at 20:55
• @user44191 Yes, $d$ is the order of $x$ in $\mathbb{Z}/n\mathbb{Z}$. Thanks for pointing that out, I've edited my post. – Mastrem Jun 10 at 21:01
• @Mastrem First of all, thank you for your contribution. I have a question though, for the natural homomorphism from $\left(\mathbb{Z}/n\mathbb{Z}\right)^{\times}$ to $\left(\mathbb{Z}/d\mathbb{Z}\right)^{\times}$, are you assuming $n$ and $d|n$ to be coprime? – L. Cardoso Jun 11 at 17:19
• @L.Cardoso No, I am not. If that were the case, the proof of surjectivity would be much easier, since then $(\mathbb{Z}/n\mathbb{Z})^\times \cong \left(\mathbb{Z}/d\mathbb{Z}\right)^\times\times \left(\mathbb{Z}/(n/d)\mathbb{Z}\right)^\times$ – Mastrem Jun 11 at 17:29
• @Mastrem OK. Running the risk of a stupid question, what is the natural homomorphism you used then? – L. Cardoso Jun 11 at 17:31