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\)