---
tag: X5KJ580184
kind: proof
name: Proof of the number of invertible residues modulo n
msc: [11A07]
proves: 06RJWZCG95
uses: [01N3AYAA6N, 0QRV8FPK5M, 019NFGFPR5, 0TPW25CBN6, 00GXTQMY8Z, 0M67FWZWPQ, 0VV04M41AN, 0GFKP8F8AG]
methods: [0NTF6DMVAP]
sources:
  - url: https://en.wikipedia.org/wiki/Modular_multiplicative_inverse
    locator: Integers modulo m
---

## Proof

1. Let $n$ be a positive integer. For an integer $a$, write $\overline{a}$ for its [[residue class|0QRV8FPK5M]] 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|01N3AYAA6N]], $\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|019NFGFPR5]] 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|00GXTQMY8Z]] modulo $n$.
7. By the [[existence of inverses modulo n|0M67FWZWPQ]], this holds if and only if $a$ and $n$ are [[coprime|0GFKP8F8AG]].
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|0VV04M41AN]], there are $\varphi(n)$ such integers $a$. Hence $\mathbb{Z}/n\mathbb{Z}$ has exactly $\varphi(n)$ invertible elements.

## Idea

Each class modulo $n$ has exactly one representative among $1, \dots, n$. A class is invertible exactly when its representative is coprime to $n$, so counting the invertible classes is counting the integers that $\varphi(n)$ counts.