[proofplan]
Every endomorphism of $\mathbb{Z}/n\mathbb{Z}$ is determined by the image of the generator $\bar{1}$, because every residue class is an integer multiple of $\bar{1}$. Such an endomorphism is an automorphism exactly when the image $\bar{a}$ again generates the additive group $\mathbb{Z}/n\mathbb{Z}$. We then prove directly that $\bar{a}$ generates $\mathbb{Z}/n\mathbb{Z}$ if and only if $\gcd(a,n)=1$, and finally check that the assignment $\varphi \mapsto \varphi(\bar{1})$ identifies composition of automorphisms with multiplication of units modulo $n$.
[/proofplan]
[step:Show that an endomorphism is determined by the image of $\bar{1}$]
Recall that a group endomorphism is a homomorphism from a group to itself. Let $\bar{k}$ denote the residue class of $k \in \mathbb{Z}$ in $\mathbb{Z}/n\mathbb{Z}$. Since the group operation on $\mathbb{Z}/n\mathbb{Z}$ is addition, we have
\begin{align*}
\bar{k}=k\bar{1}
\end{align*}
for every $k \in \mathbb{Z}$, where negative multiples are interpreted using additive inverses.
Let
\begin{align*}
\varphi: \mathbb{Z}/n\mathbb{Z} \to \mathbb{Z}/n\mathbb{Z}
\end{align*}
be a group endomorphism, and suppose $\varphi(\bar{1})=\bar{a}$ for some $a \in \mathbb{Z}$. Since $\varphi$ preserves addition and additive inverses, for every $k \in \mathbb{Z}$ we have
\begin{align*}
\varphi(\bar{k})=\varphi(k\bar{1})=k\varphi(\bar{1})=k\bar{a}=\overline{ka}.
\end{align*}
Thus $\varphi$ is uniquely determined by $\varphi(\bar{1})$.
[/step]
[step:Characterize when $\bar{a}$ generates the additive group]
We prove that $\bar{a}$ generates $\mathbb{Z}/n\mathbb{Z}$ if and only if $\gcd(a,n)=1$.
First suppose $\gcd(a,n)=1$. By the integer Bézout identity, there exist $r,s \in \mathbb{Z}$ such that
\begin{align*}
ra+sn=1.
\end{align*}
Passing to residue classes modulo $n$ gives
\begin{align*}
r\bar{a}=\bar{1}.
\end{align*}
Since $\bar{1}$ generates the additive group $\mathbb{Z}/n\mathbb{Z}$, the subgroup generated by $\bar{a}$ contains $\bar{1}$ and hence equals all of $\mathbb{Z}/n\mathbb{Z}$.
Conversely, suppose $\bar{a}$ generates $\mathbb{Z}/n\mathbb{Z}$. Then $\bar{1}$ lies in the subgroup generated by $\bar{a}$, so there exists $r \in \mathbb{Z}$ such that
\begin{align*}
r\bar{a}=\bar{1}.
\end{align*}
Equivalently, $ra \equiv 1 \pmod n$, so there exists $s \in \mathbb{Z}$ such that
\begin{align*}
ra-sn=1.
\end{align*}
Every common divisor of $a$ and $n$ divides the left-hand side $ra-sn$, hence divides $1$. Therefore $\gcd(a,n)=1$.
[guided]
The point of this step is to translate the group-theoretic condition “$\bar{a}$ is a generator” into the number-theoretic condition “$a$ is invertible modulo $n$.”
Assume first that $\gcd(a,n)=1$. The integer Bézout identity gives integers $r,s \in \mathbb{Z}$ satisfying
\begin{align*}
ra+sn=1.
\end{align*}
Modulo $n$, the term $sn$ becomes $\bar{0}$, so this identity becomes
\begin{align*}
r\bar{a}=\bar{1}.
\end{align*}
Thus the subgroup generated by $\bar{a}$ contains $\bar{1}$. But $\bar{1}$ generates the whole additive group $\mathbb{Z}/n\mathbb{Z}$, because every element has the form $\bar{k}=k\bar{1}$ for some $k \in \mathbb{Z}$. Hence $\bar{a}$ generates all of $\mathbb{Z}/n\mathbb{Z}$.
For the converse, assume that $\bar{a}$ generates $\mathbb{Z}/n\mathbb{Z}$. Since $\bar{1}$ is an element of this group, there must be some integer $r \in \mathbb{Z}$ such that
\begin{align*}
r\bar{a}=\bar{1}.
\end{align*}
This congruence means precisely that $ra-1$ is divisible by $n$. Therefore there exists $s \in \mathbb{Z}$ such that
\begin{align*}
ra-1=sn.
\end{align*}
Rearranging gives
\begin{align*}
ra-sn=1.
\end{align*}
Now let $d$ be any common divisor of $a$ and $n$. Since $d$ divides $a$, it divides $ra$; since $d$ divides $n$, it divides $sn$. Hence $d$ divides $ra-sn=1$. The only positive common divisor possible is therefore $1$, so $\gcd(a,n)=1$.
[/guided]
[/step]
[step:Identify automorphisms with generator images]
A group automorphism is a bijective [group homomorphism](/page/Group%20Homomorphism) from a group to itself. Therefore a group endomorphism
\begin{align*}
\varphi: \mathbb{Z}/n\mathbb{Z} \to \mathbb{Z}/n\mathbb{Z}
\end{align*}
is an automorphism if and only if it is surjective, because its domain and codomain are the same finite set. Its image is the subgroup generated by $\varphi(\bar{1})$, since every element of the domain has the form $k\bar{1}$ and
\begin{align*}
\varphi(\bar{k})=k\varphi(\bar{1}).
\end{align*}
Therefore $\varphi$ is an automorphism if and only if $\varphi(\bar{1})$ generates $\mathbb{Z}/n\mathbb{Z}$. By the previous step, if $\varphi(\bar{1})=\bar{a}$, this holds if and only if $\gcd(a,n)=1$.
The condition $\gcd(a,n)=1$ is independent of the chosen representative of $\bar{a}$: if $b \equiv a \pmod n$, then $b=a+qn$ for some $q \in \mathbb{Z}$, and the common divisors of $b$ and $n$ are exactly the common divisors of $a$ and $n$.
[/step]
[step:Construct the isomorphism with the unit group modulo $n$]
Here $(\mathbb{Z}/n\mathbb{Z})^\times$ denotes the multiplicative group of residue classes admitting multiplicative inverses modulo $n$, with the standard one-element convention when $n=1$. Define
\begin{align*}
\Theta: \operatorname{Aut}(\mathbb{Z}/n\mathbb{Z}) \to (\mathbb{Z}/n\mathbb{Z})^\times
\end{align*}
by
\begin{align*}
\Theta(\varphi)=\varphi(\bar{1}).
\end{align*}
The previous step shows that $\Theta(\varphi)$ is a unit modulo $n$ for every automorphism $\varphi$, so $\Theta$ is well-defined.
To prove injectivity, let $\varphi,\psi \in \operatorname{Aut}(\mathbb{Z}/n\mathbb{Z})$ and suppose $\Theta(\varphi)=\Theta(\psi)$. Then $\varphi(\bar{1})=\psi(\bar{1})$, and the first step implies $\varphi=\psi$.
To prove surjectivity, let $\bar{a} \in (\mathbb{Z}/n\mathbb{Z})^\times$. Define
\begin{align*}
\mu_a: \mathbb{Z}/n\mathbb{Z} \to \mathbb{Z}/n\mathbb{Z}
\end{align*}
by
\begin{align*}
\mu_a(\bar{k})=\overline{ak}.
\end{align*}
This map is well-defined: if $\bar{k}=\bar{\ell}$, then $n$ divides $k-\ell$, so $n$ divides $a(k-\ell)$, and hence $\overline{ak}=\overline{a\ell}$. It is a group homomorphism because, for all $k,\ell \in \mathbb{Z}$,
\begin{align*}
\mu_a(\bar{k}+\bar{\ell})=\mu_a(\overline{k+\ell})=\overline{a(k+\ell)}=\overline{ak}+\overline{a\ell}=\mu_a(\bar{k})+\mu_a(\bar{\ell}).
\end{align*}
Since $\bar{a}$ is a unit, $\gcd(a,n)=1$, so the previous step shows that $\mu_a$ is an automorphism. Also $\Theta(\mu_a)=\mu_a(\bar{1})=\bar{a}$, proving surjectivity.
Finally, let $\varphi,\psi \in \operatorname{Aut}(\mathbb{Z}/n\mathbb{Z})$, and write $\psi(\bar{1})=\bar{b}$. Then
\begin{align*}
\Theta(\varphi \circ \psi)=(\varphi \circ \psi)(\bar{1})=\varphi(\bar{b})=b\varphi(\bar{1})=\Theta(\varphi)\Theta(\psi).
\end{align*}
Thus $\Theta$ is a group homomorphism from the composition group $\operatorname{Aut}(\mathbb{Z}/n\mathbb{Z})$ to the multiplicative group $(\mathbb{Z}/n\mathbb{Z})^\times$. Since it is bijective, it is a [group isomorphism](/page/Group%20Isomorphism).
When $n=1$, the group $\mathbb{Z}/1\mathbb{Z}$ is the one-element group, its automorphism group is the one-element group, and under the standard unital convention the unit group $(\mathbb{Z}/1\mathbb{Z})^\times$ is also the one-element group. The same construction above gives the unique isomorphism in this case. This completes the proof.
[/step]
