[proofplan]
We establish the three equivalences in a cycle. The implication (i) $\Rightarrow$ (ii) is an application of [Bezout's Lemma](/theorems/???): coprimality of $a$ and $n$ produces an integer $b$ with $ab \equiv 1 \pmod n$. The reverse (ii) $\Rightarrow$ (i) observes that any such identity $ab + nk = 1$ exhibits $1$ as a $\mathbb{Z}$-linear combination of $a$ and $n$, forcing $\gcd(a, n) = 1$. For the pair (ii) $\Leftrightarrow$ (iii), we note that $a$ generates the additive group $\mathbb{Z}/n\mathbb{Z}$ iff $1 \in \langle a \rangle$ iff some integer multiple of $a$ is congruent to $1 \pmod n$, which is precisely condition (ii).
[/proofplan]
[step:Deduce (ii) from (i) via Bezout]
Assume (i): $\gcd(a, n) = 1$. By [Bezout's Lemma](/theorems/???) applied to the integers $a$ and $n$ (not both zero, since $n \geq 1$), there exist $b, c \in \mathbb{Z}$ such that
\begin{align*}
ab + nc &= \gcd(a, n) = 1.
\end{align*}
Rearranging, $ab - 1 = -nc$, so $n \mid (ab - 1)$, i.e.
\begin{align*}
ab &\equiv 1 \pmod{n}.
\end{align*}
This is (ii).
[/step]
[step:Deduce (i) from (ii) by exhibiting $1$ as a $\mathbb{Z}$-combination of $a$ and $n$]
Assume (ii): there exists $b \in \mathbb{Z}$ with $ab \equiv 1 \pmod n$. By definition of congruence mod $n$, there exists $k \in \mathbb{Z}$ with
\begin{align*}
ab - 1 &= nk, \qquad \text{i.e.,} \qquad ab + n(-k) = 1.
\end{align*}
Let $d := \gcd(a, n) \geq 1$. Since $d \mid a$ and $d \mid n$, closure of divisibility under integer linear combinations gives
\begin{align*}
d &\mid \bigl(ab + n(-k)\bigr) = 1.
\end{align*}
The only positive integer dividing $1$ is $1$, so $d = 1$, proving (i).
[guided]
Assume (ii): there exists $b \in \mathbb{Z}$ with $ab \equiv 1 \pmod n$. Unpacking the definition of congruence, $n$ divides $ab - 1$, so there exists $k \in \mathbb{Z}$ with
\begin{align*}
ab - 1 &= nk.
\end{align*}
Rearranging to isolate $1$ on one side,
\begin{align*}
1 &= ab + n(-k) = ab - nk.
\end{align*}
This displays $1$ as an integer linear combination of $a$ and $n$. The universal bound on integer linear combinations now controls the gcd. Let $d := \gcd(a, n) \geq 1$. By definition $d$ divides both $a$ and $n$, hence divides every integer linear combination of them, and in particular
\begin{align*}
d &\mid \bigl(ab + n(-k)\bigr) = 1.
\end{align*}
The only positive divisor of $1$ is $1$ itself, so $d = 1$ and (i) holds.
Why does this argument work? The passage (ii) $\Rightarrow$ (i) is essentially the "universal property" of $\gcd(a, n)$ as the generator of the ideal $\{\lambda a + \mu n : \lambda, \mu \in \mathbb{Z}\}$ — see [Every Integer Ideal is Principal](/theorems/1695). The integer $1$ lies in this ideal by (ii), hence is divisible by the generator $d$, forcing $d = 1$.
[/guided]
[/step]
[step:Translate (ii) into the additive generation statement (iii)]
Let $\bar{a} \in \mathbb{Z}/n\mathbb{Z}$ denote the residue class of $a$. The cyclic subgroup of $(\mathbb{Z}/n\mathbb{Z}, +)$ generated by $\bar{a}$ is
\begin{align*}
\langle \bar{a} \rangle &= \{m \bar{a} : m \in \mathbb{Z}\} = \{\overline{ma} : m \in \mathbb{Z}\},
\end{align*}
where $m\bar{a}$ denotes the $m$-fold additive combination of $\bar{a}$ with itself, and $\overline{ma}$ is the residue class of $ma \in \mathbb{Z}$.
The class $\bar{a}$ is a generator of $(\mathbb{Z}/n\mathbb{Z}, +)$ if and only if $\langle \bar{a} \rangle = \mathbb{Z}/n\mathbb{Z}$. Since $\mathbb{Z}/n\mathbb{Z}$ is cyclic of order $n$ generated by $\bar{1}$, the condition $\langle \bar{a} \rangle = \mathbb{Z}/n\mathbb{Z}$ is equivalent to $\bar{1} \in \langle \bar{a} \rangle$: the forward direction is immediate from equality, and the reverse holds because the subgroup containing $\bar{1}$ contains all integer multiples $\bar{1}, \bar{2}, \dots, \overline{n-1}, \bar{0}$, hence all of $\mathbb{Z}/n\mathbb{Z}$.
The statement $\bar{1} \in \langle \bar{a} \rangle$ unfolds to: there exists $m \in \mathbb{Z}$ with $\overline{ma} = \bar{1}$, i.e., $ma \equiv 1 \pmod n$. Taking $b = m$, this is precisely (ii). Conversely, (ii) with witness $b$ provides the element $m = b$ showing $\bar{1} \in \langle \bar{a} \rangle$. Thus (ii) $\Leftrightarrow$ (iii).
[guided]
We want to connect condition (ii), a multiplicative statement in $\mathbb{Z}/n\mathbb{Z}$, to condition (iii), an additive statement about generation of the cyclic group $(\mathbb{Z}/n\mathbb{Z}, +)$. The bridge is that "multiplication by $b$" in $\mathbb{Z}/n\mathbb{Z}$ is the same as "$b$-fold repeated addition".
Let $\bar{a} \in \mathbb{Z}/n\mathbb{Z}$ denote the residue class of $a$. The cyclic subgroup generated by $\bar{a}$ additively is
\begin{align*}
\langle \bar{a} \rangle &= \{m \bar{a} : m \in \mathbb{Z}\} = \{\overline{ma} : m \in \mathbb{Z}\}.
\end{align*}
Here $m\bar{a}$ means $\bar{a} + \bar{a} + \cdots + \bar{a}$ ($m$ times) for $m > 0$ (and the corresponding additive inverse for $m < 0$, with $0\bar{a} = \bar{0}$), which coincides with the residue class of the integer $ma$.
When is $\bar{a}$ a generator? By definition, when $\langle \bar{a} \rangle = \mathbb{Z}/n\mathbb{Z}$. Since $\mathbb{Z}/n\mathbb{Z}$ is itself cyclic, generated additively by $\bar{1}$, equality of subgroups is equivalent to containment of $\bar{1}$:
\begin{align*}
\langle \bar{a} \rangle = \mathbb{Z}/n\mathbb{Z} &\iff \bar{1} \in \langle \bar{a} \rangle.
\end{align*}
The forward direction is immediate. The reverse direction holds because once $\bar{1} \in \langle \bar{a} \rangle$, the subgroup $\langle \bar{a} \rangle$ must contain every integer multiple of $\bar{1}$ — that is, $\bar{0}, \bar{1}, \bar{2}, \dots, \overline{n-1}$ — and these exhaust $\mathbb{Z}/n\mathbb{Z}$.
Unfolding $\bar{1} \in \langle \bar{a} \rangle$: there exists $m \in \mathbb{Z}$ such that $m\bar{a} = \bar{1}$, equivalently $\overline{ma} = \bar{1}$, equivalently $ma \equiv 1 \pmod n$. Writing $b := m$ gives exactly condition (ii). Conversely, given (ii) with witness $b$, choosing $m := b$ shows $\bar{1} = \overline{ab} = b\bar{a} \in \langle \bar{a} \rangle$.
Thus (ii) and (iii) are tautologous once the definitions are unfolded: multiplicative invertibility of $\bar{a}$ in $\mathbb{Z}/n\mathbb{Z}$ and additive generation by $\bar{a}$ are two descriptions of the same phenomenon. The chain (i) $\Leftrightarrow$ (ii) $\Leftrightarrow$ (iii) completes the proof.
[/guided]
[/step]
