[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$.[/step]

[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: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]