# Prove that $\sigma_a \circ \sigma_b = \sigma_{ab}$.

Let $\mathbb Z_n$ be a cyclic group of order $n$ and for each integer $a$ define

$$\sigma_a : \mathbb Z_n \mapsto \mathbb Z_n, \qquad \sigma_a(x) = x^a, \quad\forall \; x \in \mathbb Z_n.$$

Prove that $\sigma_a \circ \sigma_b = \sigma_{ab}$. Deduce that the map $\bar{a} \mapsto \sigma_a$ is an isomorphism of ($\mathbb{Z} / n \mathbb{Z})^{\times}$ onto the automorphism group of $\mathbb Z_n$ (so $Aut(\mathbb Z_n)$ is an abelian group of order $\phi(n)$).

The question is section 2.3 question 26 part d page 75 of Dummitt and Foote's Abstract Algebra.

Understand the other parts, but this one has me a bit baffled.

Define a mapping $\Phi : (\mathbb{Z}/n\mathbb{Z})^\times \rightarrow \mathsf{Aut}\ Z_n$ by $\Phi(\overline{a}) = \sigma_a$. Since, $\sigma_a = \sigma_b$ if and only if $a \equiv b$ $mod$ $n$, $\Phi$ is well defined.

Moreover, letting $x \in Z_n$ be arbitrary, we have $(\sigma_a \circ \sigma_b)(x) = \sigma_a(\sigma_b(x)) = \sigma_a(x^b) = (x^b)^a = x^{ab} = \sigma_{ab}(x)$.

Thus, $\sigma_a \circ \sigma_b = \sigma_{ab}$.

In other words, $\Phi(\overline{a} \overline{b}) = \Phi(\overline{a}) \Phi(\overline{b})$.

Thus $\Phi$ is a homomorphism.

Finally, since every automorphism of $Z_n$ is equal to $\sigma_a$ for some $a$, $\phi$ is surjective. Since $\mathsf{Aut}\ Z_n$ and $(\mathbb{Z}/n\mathbb{Z})^\times$ are finite $\phi$ is bijective. Thus $\Phi$ is an isomorphism.

If you understand the other parts of this problem, then you're practically finished. Indeed, in parts (a) - (c) you've essentially already shown that

$\sigma \in \text{Aut}(Z_n) \iff \sigma = \sigma_a$ for some $a$ coprime to $n$

(Note this is $\iff$ not just $\implies$ by combining (a) and (c).)

and also

$\sigma_a = \sigma_b \iff a\equiv b \pmod{n}$

Combining these two statements you can conclude (how?) that $$\text{Aut}(Z_n) = \{\sigma_a : 1 \leq a \leq n-1, \text{gcd}(a,n) = 1\}.$$ Accordingly, there is a bijection $$\Phi: (\mathbb{Z}/n\mathbb{Z})^\times \to \text{Aut}(Z_n)$$ given by $\Phi(\overline{a}) = \sigma_a$ for all $a$ coprime to $n$, where for $a \in \mathbb{Z}$ we denote by $\overline{a}$ the equivalence class of $a$ modulo $n$. (This is well-defined by the second property above.) Since the domain of $(\mathbb{Z}/n\mathbb{Z})^\times$ is a multiplicative group, it's natural to ask whether or not $\Phi$ is a homomorphism (and hence an isomorphism). This can be stated more succinctly as checking whether or not $\Phi(\overline{a}\overline{b}) = \Phi(\overline{a})\circ\Phi(\overline{b})$, or (equivalently) $\sigma_{ab} = \sigma_a\circ\sigma_b$ (where composition of functions $\circ$ is used on the right since it's the natural group operation on $\text{Aut}(Z_n)$.

So you need to determine if for each $x \in Z_n$ it's true that $\sigma_{ab}(x) = \sigma_a(\sigma_b(x))$. Do you see why this is true given the definition of $\sigma_c$?

This is (intentionally) more of a guide and some perspective than a proof. Try to work through the result. I'm happy to answer additional questions.