[proofplan] We prove the equivalence by translating invertibility in the quotient ring into a congruence. The forward direction uses a Bezout certificate for coprimality to construct an explicit inverse modulo $n$, while the reverse direction shows that a modular inverse forces every common divisor of $a$ and $n$ to divide $1$. Finally, each residue class modulo $n$ has a unique representative in $\{1,\dots,n\}$, and the equivalence identifies the units with precisely the representatives counted by $\varphi(n)$. [/proofplan] [step:Construct a modular inverse from a Bezout certificate] Assume that $\gcd(a,n)=1$. We first record the elementary Bezout fact needed in this special case. [claim:Bezout certificate for coprime integers] There exist integers $x,y\in\mathbb{Z}$ such that \begin{align*} ax+ny=1. \end{align*} [/claim] [proof] Let \begin{align*} S=\{au+nv:u,v\in\mathbb{Z}\text{ and }au+nv>0\}. \end{align*} Since $n\ge 1$, the set $S$ is nonempty because $n=a\cdot 0+n\cdot 1\in S$. By the [well-ordering principle](/theorems/721), $S$ has a least element; denote it by $m$. Choose $x,y\in\mathbb{Z}$ such that \begin{align*} m=ax+ny. \end{align*} Divide $a$ by $m$ in $\mathbb{Z}$. Thus there exist $q,r\in\mathbb{Z}$ with $0\le r<m$ and \begin{align*} a=qm+r. \end{align*} Then \begin{align*} r=a-qm=a-q(ax+ny)=a(1-qx)+n(-qy). \end{align*} If $r>0$, then $r\in S$, contradicting the minimality of $m$. Hence $r=0$, so $m\mid a$. Divide $n$ by $m$ in $\mathbb{Z}$. Thus there exist $q',r'\in\mathbb{Z}$ with $0\le r'<m$ and \begin{align*} n=q'm+r'. \end{align*} Then \begin{align*} r'=n-q'm=n-q'(ax+ny)=a(-q'x)+n(1-q'y). \end{align*} If $r'>0$, then $r'\in S$, contradicting the minimality of $m$. Hence $r'=0$, so $m\mid n$. Since $\gcd(a,n)=1$, every common positive divisor of $a$ and $n$ divides $1$, and therefore $m=1$. Thus $1=ax+ny$ for the chosen integers $x,y$. [/proof] Let $\bar{x}=x+n\mathbb{Z}$ denote the residue class of $x$ in $\mathbb{Z}/n\mathbb{Z}$. From $ax+ny=1$ we get \begin{align*} ax-1=-ny. \end{align*} Thus $n\mid(ax-1)$, so $ax\equiv 1\pmod n$. Multiplication in the quotient ring gives \begin{align*} \bar{a}\bar{x}=\overline{ax}=\bar{1}. \end{align*} Since $\mathbb{Z}/n\mathbb{Z}$ is commutative, also $\bar{x}\bar{a}=\bar{1}$. Hence $\bar{a}$ is a unit in $\mathbb{Z}/n\mathbb{Z}$. [guided] Assume that $\gcd(a,n)=1$. To prove that $\bar{a}$ is a unit, we need to produce an element of $\mathbb{Z}/n\mathbb{Z}$ whose product with $\bar{a}$ is the multiplicative identity $\bar{1}$. The bridge from coprimality to an inverse is a Bezout certificate. Define \begin{align*} S=\{au+nv:u,v\in\mathbb{Z}\text{ and }au+nv>0\}. \end{align*} This set is nonempty because $n=a\cdot 0+n\cdot 1$ and $n\ge 1$. By the well-ordering principle, $S$ has a least element; call it $m$. Choose integers $x,y\in\mathbb{Z}$ such that \begin{align*} m=ax+ny. \end{align*} We show that $m$ divides both $a$ and $n$. Divide $a$ by $m$, so there exist $q,r\in\mathbb{Z}$ with $0\le r<m$ and \begin{align*} a=qm+r. \end{align*} Substituting $m=ax+ny$ gives \begin{align*} r=a-qm=a-q(ax+ny)=a(1-qx)+n(-qy). \end{align*} Thus $r$ is again an integer linear combination of $a$ and $n$. If $r>0$, then $r\in S$, but $r<m$, contradicting the minimality of $m$. Therefore $r=0$, so $m\mid a$. We also prove directly that $m\mid n$. Divide $n$ by $m$, so there exist $q',r'\in\mathbb{Z}$ with $0\le r'<m$ and \begin{align*} n=q'm+r'. \end{align*} Substituting $m=ax+ny$ gives \begin{align*} r'=n-q'm=n-q'(ax+ny)=a(-q'x)+n(1-q'y). \end{align*} Thus $r'$ is an integer linear combination of $a$ and $n$. If $r'>0$, then $r'\in S$ and $r'<m$, again contradicting the minimality of $m$. Hence $r'=0$, so $m\mid n$. Now $m$ is a positive common divisor of $a$ and $n$. Since $\gcd(a,n)=1$, we must have $m=1$. Therefore the chosen integers $x,y\in\mathbb{Z}$ satisfy \begin{align*} ax+ny=1. \end{align*} Let $\bar{x}=x+n\mathbb{Z}$ be the residue class of $x$ modulo $n$. From $ax+ny=1$ we obtain $ax-1=-ny$, so $n\mid(ax-1)$ and hence $ax\equiv 1\pmod n$. Passing to the quotient ring, \begin{align*} \bar{a}\bar{x}=\overline{ax}=\bar{1}. \end{align*} Because $\mathbb{Z}/n\mathbb{Z}$ is commutative, this also gives $\bar{x}\bar{a}=\bar{1}$. Thus $\bar{x}$ is a multiplicative inverse of $\bar{a}$, so $\bar{a}\in(\mathbb{Z}/n\mathbb{Z})^\times$. [/guided] [/step] [step:Recover coprimality from a modular inverse] Assume that $\bar{a}\in(\mathbb{Z}/n\mathbb{Z})^\times$. Then there exists a residue class $\bar{b}\in\mathbb{Z}/n\mathbb{Z}$, with representative $b\in\mathbb{Z}$, such that \begin{align*} \bar{a}\bar{b}=\bar{1}. \end{align*} Equivalently, \begin{align*} \overline{ab}=\bar{1}, \end{align*} so $ab\equiv 1\pmod n$. Therefore there exists $t\in\mathbb{Z}$ such that \begin{align*} ab-1=nt. \end{align*} Let $d=\gcd(a,n)$. Since $d\mid a$ and $d\mid n$, we have $d\mid ab$ and $d\mid nt$. Hence $d\mid(ab-nt)$. Using $ab-nt=1$, we obtain $d\mid 1$. Since $d$ is a positive integer, this forces $d=1$. Therefore $\gcd(a,n)=1$. [/step] [step:Check that the reduced condition depends only on the residue class] Let $a,a'\in\mathbb{Z}$ satisfy $\bar{a}=\bar{a'}$ in $\mathbb{Z}/n\mathbb{Z}$. Then $n\mid(a-a')$, so there exists $s\in\mathbb{Z}$ such that \begin{align*} a'=a+ns. \end{align*} If $\gcd(a,n)=1$, then the first step shows that $\bar{a}$ is a unit. Since $\bar{a'}=\bar{a}$, the class $\bar{a'}$ is also a unit. Applying the previous step to $a'$ gives $\gcd(a',n)=1$. Reversing the roles of $a$ and $a'$ gives the converse. Hence $\gcd(a,n)=1$ is invariant under replacing $a$ by a congruent integer modulo $n$. Combining the first two steps gives \begin{align*} \bar{a}\in(\mathbb{Z}/n\mathbb{Z})^\times \iff \gcd(a,n)=1. \end{align*} The displayed description of $(\mathbb{Z}/n\mathbb{Z})^\times$ follows immediately. [/step] [step:Count units by the standard representatives] For each residue class $\bar{a}\in\mathbb{Z}/n\mathbb{Z}$, the [division algorithm](/theorems/725) gives unique integers $q,r\in\mathbb{Z}$ such that $a=qn+r$ and $0\le r<n$. Define $k=r$ if $1\le r\le n-1$, and define $k=n$ if $r=0$. Then $k\in\{1,\dots,n\}$ and $\bar{k}=\bar{a}$. The representative $k$ is unique in $\{1,\dots,n\}$ because if $k,\ell\in\{1,\dots,n\}$ and $\bar{k}=\bar{\ell}$, then $n\mid(k-\ell)$, while $|k-\ell|<n$, so $k-\ell=0$. Thus the map sending a residue class to its unique representative in $\{1,\dots,n\}$ is a bijection between $\mathbb{Z}/n\mathbb{Z}$ and $\{1,\dots,n\}$. By the equivalence already proved, this bijection restricts to a bijection \begin{align*} (\mathbb{Z}/n\mathbb{Z})^\times \longleftrightarrow \{k\in\{1,\dots,n\}:\gcd(k,n)=1\}. \end{align*} Taking cardinalities and using the defining formula for $\varphi(n)$ gives \begin{align*} \left|(\mathbb{Z}/n\mathbb{Z})^\times\right|=\varphi(n). \end{align*} When $n=1$, the same argument gives the unique representative $k=1$, the quotient ring has its single element as the identity element, and the displayed cardinality is $1=\varphi(1)$. This completes the proof. [/step]