Exercise 931Number theory › Divisibility and gcdL1Added 3 Nov 2026

Units modulo $n$

#units#invertible#Euler totient

Statement

Show that $\bar a\in\mathbb{Z}/n\mathbb{Z}$ is invertible iff $\gcd(a,n)=1$ .

Hint

$\bar a$ invertible means $\bar a\bar b=\bar1$ for some $b$ , i.e. $ab\equiv1\pmod n$ .

Show solutionHide solution

If invertible. $ab\equiv1\pmod n$ means $ab=1+kn$ , so $ab-kn=1$ . Any common divisor of $a,n$ divides $1$ , so $\gcd(a,n)=1$ .

If coprime. Bézout: $au+nv=1$ , so $au\equiv1\pmod n$ , i.e. $\bar a\bar u=\bar1$ .

Conclusion. The units of $\mathbb{Z}/n\mathbb{Z}$ are exactly the classes of integers coprime to $n$ ; there are $\varphi(n)$ of them.