Exercise 1132Number theory › PrimesL1Added 3 Nov 2026

Totient and coprime residue classes

#totient#coprime#residue classes

Statement

Show that $\varphi(n)$ counts the integers $1\le k\le n$ with $\gcd(k,n)=1$ , equivalently the units of $\mathbb{Z}/n\mathbb{Z}$ .

Hint

Residues mod $n$ are in bijection with $\{1,\ldots,n\}$ ; the class of $k$ is invertible iff $\gcd(k,n)=1$ .

Show solutionHide solution

Bijection. $\{1,\ldots,n\}\to\mathbb{Z}/n\mathbb{Z}$ , $k\mapsto k\bmod n$ .

Units. $\bar k$ is a unit iff $\gcd(k,n)=1$ .

Conclusion. $\varphi(n)=|\{k\in\{1,\ldots,n\}:\gcd(k,n)=1\}|=|\mathbb{Z}/n\mathbb{Z}^*|$ .