# Confusing step in proof of property of cyclic group automorphisms

Let $C_n = \{1, x, \dots, x^{n-1}\}$ and define $\varphi_r : C_n \to C_n$ as $\varphi_r(x^s) = x^{rs}$.

Theorem: $\varphi_r$ is bijective $\iff$ $\gcd(r,n)=1$.

This is the proof given in a set of notes I'm using:

$\varphi_r$ is bijective $\iff \varphi_r$ is surjective $\iff$ $\{\varphi(x)^t : 0 \leq t < n\} = C_n \iff \mathrm{ord}( \varphi_r(x)) = n \iff \frac{n}{\gcd(r,n)} = n \iff \gcd(r,n)=1$

I'm confused by the step $\{\varphi(x)^t : 0 \leq t < n\} = C_n \iff \mathrm{ord}( \varphi_r(x)) = n$. What is the justification for this?

It is because the image of $\phi$ is generated by $\phi_r(x)$. So $\phi_r$ is surjective is equivalent to the fact that $x,\phi_r(x),...,\phi_r(x)^{n-1}$ are distinct.
• How does distinctness of $x, \varphi_r(x), \dots, \varphi_r(x)^{n-1}$ demonstrate that $ord(\varphi_r(x)) = n$? – D G Jan 16 '18 at 9:56
• because the order of $\phi_r(x)$ divides $n$ (Lagrange). – Tsemo Aristide Jan 16 '18 at 9:58
Clearly, $\varphi_r(x)$ generates the image of $\varphi_r$, so the map is surjective if and only if $\varphi_r(x)$ has order $n$. The set $$\{\varphi_r(x)^t:0\le t<n\}=\{\varphi_r(x^t):0\le t<n\}$$ is the image of $\varphi_r$.
By general results, the order of $x^r$ is $n/\!\gcd(n,r)$.