If $y\in {\mathbb{Z}}_n$ is invertible (that is, if $y^{-1}$ exists), then we say $y$ is a unit. The set of units of ${\mathbb{Z}}_n$ is denoted by ${\mathbb{Z}}_n^{*}$, or ${\mathbb{Z}}_n^{\times }$.

We know $y$ is a unit if and only if $y$ and $n$ are coprime. So the size of ${\mathbb{Z}}_n^{*}$ is precisely the number of integers in $\{1,...,n-1\}$ that are coprime to $n$.

We write $\varphi (n)$ for the number of elements of ${\mathbb{Z}}_n^{*}$. The function $\varphi (n)$ is called the Euler totient function. Actually, it turns out to be convenient to have $\varphi (1)=1$, so we prefer to define $\varphi (n)$ as the number of integers in $\{1,...,n\}$ coprime to $n$. (This agrees with our original definition except when $n=1$.)

Examples: $\varphi (6)=2$ since among $\{\mathrm{1,...,6}\}$ only $1$ and $5$ are coprime to $6$, and thus are the only units in ${\mathbb{Z}}_6$.

Let $p$ be a prime. Then every nonzero element $a\in {\mathbb{Z}}_p$ is coprime to $p$ (and hence a unit) thus we have $\varphi (p)=p-1$.

How about powers of primes? If $p$ is a prime, then the only numbers not coprime to $p^k$ are the multiples of $p$, and there are $p^k/p=p^{k-1}$ of these. Hence

Now let $m,n$ be coprime, and let $x\in {\mathbb{Z}}_{mn}$. Let $a=x(modm)$ and $b=x(modn)$ (we reduce $x$ modulo $p$ and $q$). Then by the Chinese Remainder Theorem, $x$ is a unit if and only if $a$ and $b$ are. Thus ${\mathbb{Z}}_{pq}^{*}={\mathbb{Z}}_p^{*}\times {\mathbb{Z}}_q^{*}$.

Looking at the size of these sets gives this fact: for $p,q$ coprime, we have

(Thus $\varphi$ is multiplicative.)

Putting this together with the previous statement $\varphi (p^k)=p^k-p^{k-1}$ for prime $p$, we get that for any integer $n=p_1^{k_1}...p_m^{k_m}$ (where we have factorized $n$ into primes) we have

Often this formula is rewritten as