If r is a primitive root, then the residue of $r^t$ is also a primitive root if $\gcd(t,\phi(m))=1$ where $\phi$ is Euler's totient

Question

This is part ii of the proof of Proposition 6.77 of Gerstein's Introduction to Mathematical Structures and Proofs. I don't understand it. Here is how the discussion, and my understanding of it, go:

$r$ is a primitive root

$(a,b)$ represents $\gcd(a,b)$.

$Z=\{x\mid (x,m)=1 \land 1\le x \lt m\}$

Suppose $(t,\phi(m))=1$. Then $r\equiv (r^t)^x$ for some $x$. I see this.

Since $r$ is equal to its residue, we have the residue of $(r^t)^x$ equal to $r$.

Then they go on to state "... hence every element of $Z$ is congruent to a power of $r^t$." I don't see this. They may be applying part i, which says

$Z$ consists of the residues of the powers of $r^t$ with $1\le t \le \phi(m)$

This would imply that $r\in Z$, which we already knew.

Answer 1

The definition of a primitive root is

... $g$ is a primitive root modulo $n$ if every number $a$ coprime to $n$ is congruent to a power of $g$ modulo $n$.

Since it's stated that $r$ is a primitive root modulo $m$, and $Z$ includes only numbers coprime to $m$ in $[1, m-1]$, for each element $y$ of $Z$ there's an integer $s$ where

$$y \equiv r^s \pmod{m} \tag{1}\label{eq1A}$$

Using what you stated, i.e., $r \equiv (r^t)^x = r^{tx} \pmod{m}$ for some $x$, in \eqref{eq1A} gives

$$y \equiv (r^{tx})^s = r^{txs} = (r^t)^{xs} \pmod{m} \tag{2}\label{eq2A}$$

Answer 2

I don't understand what exactly is going on in the proof that you quoted because the quote is incomplete. If you don't mind a different proof, then I recommend proving and using the more general fact that $$\text{ord}_{n}(a^k)=\frac{\text{ord}_{n}(a)}{\gcd(k,\text{ord}_{n}(a))}.$$ It is pretty easy to see from this that the powers of a primitive root $g$ modulo $n$ that are also primitive roots are exactly the $g^k$ such that $\gcd(k,\varphi(n))=1.$