Group action and orbit question

Question

I have the following group action question that I would like some advice on how should i proceed.

Let $X$ be the group $\mathbb{Z}/n\mathbb{Z}$ and $G$ be the group $(\mathbb{Z}/n\mathbb{Z})^*$. Let $G$ act on $X$ via

$$g\cdot x=gx$$

Given $m\in X$, show that the orbit containing $m$ is the same as the orbit containing $d$ where $(m,n)=d$.

I have tried using the following to solve it to no avail.

1. Bezout's identity: There exists $a,b\in \mathbb{Z}$ such that $am+bn=d$
2. Let $a,b>0$ be integers and $d = (a, b)$. Suppose $d|N$. Then the linear congruence

$$ax \equiv N (\text{mod }b)$$

$\space\space\space\space\space\space\space$ has $d$ mutually incongruent solutions modulo $b$.

Does anybody have any advice on how I should solve this?

Answer 1

After getting some inspiration from @Compacto to use the Chinese Remainder Theorem, I have managed to think of a solution.

Let $n=p_{1}^{\alpha_1}p_{2}^{\alpha_2}...p_{k}^{\alpha_k}$ be the prime factor decomposition of $n$.

By the Chinese Remainder Theorem, we have an isomorphic map

$$f:\mathbb{Z}/n\mathbb{Z}\rightarrow(\mathbb{Z}/p_{1}^{\alpha_1}\mathbb{Z})\times(\mathbb{Z}/p_{2}^{\alpha_2}\mathbb{Z})\times...\times(\mathbb{Z}/p_{k}^{\alpha_k}\mathbb{Z})$$

defined by $f(x)=(x\space\text{mod}\space p_{1}^{\alpha_1},x\space\text{mod}\space p_{2}^{\alpha_2},...,x\space\text{mod}\space p_{k}^{\alpha_k})$.

Let $f(d)=(d_1,d_2,...,d_k)$ and $f(m)=(m_1,m_2,...,m_k)$, where $d=\text{gcd}(m,n)$. Since $d|m$, $d_i|m_i$.

We claim that $p_{i}^{\beta_i}||d_i\Rightarrow p_{i}^{\beta_i}||m_i$. The proof is as follows:

\begin{aligned} p_{i}^{\beta_i}||d_i &\Rightarrow p_{i}^{\beta_i}||d\space\because\space d_i\equiv d\space(\text{mod}\space p_i^{\alpha_i})\\ &\Rightarrow p_{i}^{\beta_i}||m\because\space d=\gcd(m,n) \text{ and }p_i^{\alpha_i}|n\\ &\Rightarrow p_{i}^{\beta_i}||m_{i}\space\because\space m_i\equiv m\space(\text{mod}\space p_i^{\alpha_i}) \end{aligned}

Since $d_i|m_i$ and $p_{i}^{\beta_i}||d_i\Rightarrow p_{i}^{\beta_i}||m_i$, $e_i d_i=m_i$, where $p_i\nmid e_i$. Hence, $e_i$ is invertible in $\mathbb{Z}/p_i^{\alpha_i}\mathbb{Z}$.

Therefore, $(e_1,e_2,...,e_k)(d_1,d_2,...,d_k)=(m_1,m_2,...,m_k)$, where $(e_1,e_2,...,e_k)$ is invertible in $(\mathbb{Z}/p_{1}^{\alpha_1}\mathbb{Z})\times(\mathbb{Z}/p_{2}^{\alpha_2}\mathbb{Z})\times...\times(\mathbb{Z}/p_{k}^{\alpha_k}\mathbb{Z})$. This means that there is an invertible $e\in \mathbb{Z}/n\mathbb{Z}$ such that $f(e)=(e_1,e_2,...,e_k)$ and $ed=m$ where $e\in(\mathbb{Z}/n\mathbb{Z})^*$.

This means that $d$ and $m$ are in the same orbit as desired. (Shown)

Answer 2

I think an approach based on the Chinese remainder theorem might work.

Let

$n = p_1^{q_1}... p_r^{q_r}$

be the prime factor decomposition for $n$. From the chinese remainder theorem, we have:

$\mathbb{Z}/n\mathbb{Z} \cong \mathbb{Z}/p_1^{q_1}\mathbb{Z}\times ... \times \mathbb{Z}/p_r^{q_r}\mathbb{Z}$.

Let $m = (m_1,...,m_r)$, and let $e=(e_1,...,e_r)$ such that

$e_i = gcd(p_i^{q_i},m_i)$.

Since $e_i$ divides $p_i^{q_i}$ in $\mathbb{Z}/p_i^{q_i}\mathbb{Z}$, it must be a power of $p_i$ (the largest one which divides $m_i$), and we have $m_i = k_i e_i$, where $k_i$ can't be divided by $p_i$ and so is invertible.

This implies that $m = ke$ where $k = (k_1,...,k_r)$ is invertible. We will now see that

$d= ge$, for some invertible $g$.

Let $d = (d_1,...,d_r)$. We must see that $d_i$ is equal to the largest power of $p_i$ that divides $m_i$ up to invertibles. Since $d$ divides $n$, $dl = n$ implies $d_il_i = 0$. (Correction by Explorer: there are two cases).

If $l_i\neq 0$, then $d_i$ is not prime with $p_i^{q_i}$ and so, it must be a prime power of exponent $\leq$ $e_i$ times invertibles. But due to Bezout's identity, $d= am = ake = ce$, which means that $d_i = c_i e_i$ and thus, $e_i$ divides $d_i$, and so, the exponents must be equal by Euclid's lemma.

If $l_i=0$, then $d_i$ is invertible and can't be divided by $p_i$, so neither can $m$, which implies that $e_i$ is invertible as well. Since both $e_i$ and $d_i$ are invertible, they differ by an invertible element $g_i= d_ie_i^{-1}$.