## Units and the Totient Function

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

Examples: $\phi(6) = 2$ since among $\{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 $\phi(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

$\phi(p^k) = p^k - p^{k-1}$

Now let $m, n$ be coprime, and let $x \in \mathbb{Z}_{m n}$. Let $a = x \pmod{m}$ and $b = x \pmod{n}$ (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}_{p q}^* = \mathbb{Z}_p^* \times \mathbb{Z}_q^*$.

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

$\phi(p q) = \phi(p) \phi(q).$

(Thus $\phi$ is multiplicative.)

Putting this together with the previous statement $\phi(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

$\phi(n) = (p_1^{k_1} - p_1^{k_1 - 1})...(p_m^{k_m} - p_m^{k_m-1})$

Often this formula is rewritten as

$\phi(n) = n{(1 - \frac{1}{p_1})}...{(1-\frac{1}{p_m})}$