Proof of the number of invertible residues modulo n

Proof

1. Let $n$ be a positive integer. For an integer $a$, write $\overline{a}$ for its residue class modulo $n$. Then $\overline{a} = \overline{b}$ if and only if $a \equiv b \pmod n$.
2. The classes $\overline{1}, \overline{2}, \dots, \overline{n}$ are distinct. Indeed, two different integers in $\{ 1, \dots, n \}$ differ by a number between $1$ and $n - 1$, which $n$ does not divide.
3. Since $n \equiv 0 \pmod n$, we have $\overline{n} = \overline{0}$. So by the definition of integers modulo n, $\mathbb{Z}/n\mathbb{Z} = \{ \overline{1}, \overline{2}, \dots, \overline{n} \}$.
4. Let $a$ be an integer. The class $\overline{a}$ is a unit if there is an integer $x$ with $\overline{a} \cdot \overline{x} = \overline{1}$. The ring is commutative, so one side suffices.
5. Since $\overline{a} \cdot \overline{x} = \overline{a x}$, step 1 shows that $\overline{a} \cdot \overline{x} = \overline{1}$ if and only if $a x \equiv 1 \pmod n$.
6. So $\overline{a}$ is invertible if and only if $a$ has a modular multiplicative inverse modulo $n$.
7. By the existence of inverses modulo n, this holds if and only if $a$ and $n$ are coprime.
8. By steps 3 and 7, the invertible elements are the classes $\overline{a}$ with $1 \le a \le n$ and $a$ coprime to $n$. By step 2, these classes are distinct.
9. By the definition of Euler's totient function, there are $\varphi(n)$ such integers $a$. Hence $\mathbb{Z}/n\mathbb{Z}$ has exactly $\varphi(n)$ invertible elements.