Deduce that $\mbox{Aut}(\mathbb{Z}/n\mathbb{Z})$ is isomorphic to $(\mathbb{Z}/n\mathbb{Z})^*$ (a group under multiplication) Deduce that $\mbox{Aut}(\mathbb{Z}/n\mathbb{Z})$ is isomorphic to $(\mathbb{Z}/n\mathbb{Z})^*$ (a group under multiplication)
I can see $\mathbb{Z}/n\mathbb{Z}$ is spanned by $1$. But I don't know how to proceed.
 A: Let $\mbox{End}(\mathbb{Z}/n\mathbb{Z})$ be the set of homomorphisms from $\mathbb{Z}/n\mathbb{Z}$ to itself. Any $f \in \mbox{End}(\mathbb{Z}/n\mathbb{Z})$ is completely determined by $f(1)$ (why?). Actually, this gives a bijection between $\mbox{End}(\mathbb{Z}/n\mathbb{Z})$ and $\mathbb{Z}/n\mathbb{Z}$.
Let $f \in \mbox{End}(\mathbb{Z}/n\mathbb{Z})$ and $a=f(1) \in \mathbb{Z}/n\mathbb{Z}$.
It turns out that $a$ is invertible in $\mathbb{Z}/n\mathbb{Z}$ iff $f$ is an automorphism. Indeed, if $a$ is invertible, then $g \in \mbox{End}(\mathbb{Z}/n\mathbb{Z})$ such that $g(1)=a^{-1}$ is the inverse of $f$ (why?). On the other hand, if $f$ is an automorphism and $g$ is its inverse, then $g(1)$ is the inverse of $a$ (why?).
It is easy to show that this correspondence between $\mbox{Aut}(\mathbb{Z}/n\mathbb{Z})$ and $(\mathbb{Z}/n\mathbb{Z})^*$ is a homomorphism.

Another way to get to the solution using monoids:
$\mbox{End}(\mathbb{Z}/n\mathbb{Z})$ is a monoid with multiplication given by function composition and $\mathbb{Z}/n\mathbb{Z}$ is a monoid with the multiplication modulo $n$. The map sending $f \in \mbox{End}(\mathbb{Z}/n\mathbb{Z})$ to $f(1) \in \mathbb{Z}/n\mathbb{Z}$ is actually an isomorphism of monoids. This isomorphism restricts to an isomorphism of groups between the groups of the invertible elements. Those are exactly $\mbox{Aut}(\mathbb{Z}/n\mathbb{Z})$ and $(\mathbb{Z}/n\mathbb{Z})^*$.
