Let $n, m \in \mathbb{Z}$, where $n \gt 0$, and let $d := gcd(m,\varphi(n))$. Show that:

(a) if $d =1$, then $(\mathbb{Z_n^*})^m = (\mathbb{Z_n^*})$;
(b) if $\alpha \in (\mathbb{Z_n^*})^m$, then $\alpha^{\varphi(n)/d} = 1$.

== Attempt ==

For (a), consider Theorem 2.17 in Shoup:

Let $n$ be a positive integer. For each $\alpha \in \mathbb{Z_n^*}$, and all $l, m \in \mathbb{Z}$ with $gcd(l,m) = 1$, if $\alpha^l \in (\mathbb{Z_n^*})^m$, then $\alpha \in (\mathbb{Z_n^*})^m$

Given $d = gcd(m,\varphi(n)) = 1$, setting $l := \varphi(n)$, this means for each $\alpha \in \mathbb{Z_n^*}$, if $\alpha^{\varphi(n)} \in (\mathbb{Z_n^*})^m$, then $\alpha \in (\mathbb{Z_n^*})^m$. But by Euler's theorem, $\alpha^{\varphi(n)} \equiv 1 \pmod n$ and $1 = 1^m \in (\mathbb{Z_n^*})^m$. In other words, all members of $\mathbb{Z_n^*}$ are also members of $(\mathbb{Z_n^*})^m$. Therefore $(\mathbb{Z_n^*})^m = (\mathbb{Z_n^*})$.

For (b), consider Theorem 2.15 in Shoup:

Suppose $\beta \in \mathbb{Z_n^*}$ has multiplicative order $k$. Then for every $m \in \mathbb{Z}$, the multiplicative order of $\beta^m$ is $\displaystyle\frac{k}{gcd(m,k)}$

Let $\alpha \equiv \beta^m \pmod n$ and $k$ be the multiplicative order of $\beta$, then the multiplicative order of $\alpha$ is $\displaystyle k' = \frac{k}{gcd(m,k)}$. It remains to show that $k'$ divides $\displaystyle\frac{\varphi(n)}{d} = \frac{\varphi(n)}{gcd(m,\varphi(n))}$.

By Euler's theorem, we know that $k$ divides $\varphi(n)$. Let $k \cdot l = \varphi(n)$ for some positive integer $l$.

Consider:

$$\begin{aligned} \frac{\varphi(n)}{gcd(m,\varphi(n))} \div k' &= \frac{\varphi(n)}{gcd(m,\varphi(n))} \cdot \frac{gcd(m,k)}{k} \\ &= \frac{\varphi(n)}{gcd(m, kl)} \cdot \frac{gcd(m,k)}{k} \\ &= \frac{\varphi(n)}{gcd(m, l)} \cdot \frac{1}{k} \end{aligned}$$

Since $gcd(m, l) \mid l$, $k \cdot gcd(m, l) \mid kl = \varphi(n)$. This shows that $k'$, the multiplicative order of $\alpha$, divides $\displaystyle\frac{\varphi(n)}{d}$. Therefore $\alpha^{\varphi(n)/d} = 1$. $\Box$