[proofplan] We translate invertibility modulo $n$ into an integer divisibility condition, then into a Bézout identity. The [GCD as Linear Combination](/theorems/727) identifies the existence of such a Bézout identity with $\gcd(a,n)=1$. Reversing these equivalences gives exactly the desired if and only if statement. [/proofplan] [step:Translate a Bézout identity into a modular inverse] By GCD as Linear Combination, applied to the integers $a$ and $n$ with target value $1$, we have \begin{align*} \gcd(a,n)=1 \iff \exists\, x,y \in \mathbb{Z} \text{ such that } ax+ny=1. \end{align*} For integers $x,y \in \mathbb{Z}$, the equation $ax+ny=1$ is equivalent, by rearranging terms, to \begin{align*} ax-1=-ny. \end{align*} Since $-y \in \mathbb{Z}$, this is equivalent to $n \mid (ax-1)$, which by the definition of congruence modulo $n$ is equivalent to \begin{align*} ax \equiv 1 \pmod n. \end{align*} Therefore \begin{align*} \gcd(a,n)=1 \iff \exists\, x \in \mathbb{Z} \text{ such that } ax \equiv 1 \pmod n. \end{align*} [guided] We want to connect the arithmetic condition $\gcd(a,n)=1$ with the existence of a modular inverse. The bridge is GCD as Linear Combination, used for the two integers $a$ and $n$ and the target value $1$. It gives \begin{align*} \gcd(a,n)=1 \iff \exists\, x,y \in \mathbb{Z} \text{ such that } ax+ny=1. \end{align*} Now suppose $x,y \in \mathbb{Z}$ satisfy $ax+ny=1$. Subtracting $1$ and moving the term $ny$ to the other side gives \begin{align*} ax-1=-ny. \end{align*} Because $-y$ is also an integer, this says exactly that $n$ divides $ax-1$. By the definition of congruence modulo $n$, the divisibility condition $n \mid (ax-1)$ is equivalent to \begin{align*} ax \equiv 1 \pmod n. \end{align*} Conversely, if there exists $x \in \mathbb{Z}$ with $ax \equiv 1 \pmod n$, then by the definition of congruence modulo $n$ there exists $k \in \mathbb{Z}$ such that \begin{align*} ax-1=nk. \end{align*} Setting $y := -k \in \mathbb{Z}$ gives \begin{align*} ax+ny=1. \end{align*} The GCD as Linear Combination then gives $\gcd(a,n)=1$. Hence \begin{align*} \gcd(a,n)=1 \iff \exists\, x \in \mathbb{Z} \text{ such that } ax \equiv 1 \pmod n. \end{align*} [/guided] [/step] [step:Identify the congruence condition with being a unit modulo $n$] By the definition stated in the theorem, $a$ is a unit modulo $n$ precisely when there exists $x \in \mathbb{Z}$ such that \begin{align*} ax \equiv 1 \pmod n. \end{align*} Combining this definition with the equivalence proved above gives \begin{align*} a \text{ is a unit modulo } n \iff \gcd(a,n)=1. \end{align*} This proves the claim. [/step]