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})}$

Ben Lynn blynn@cs.stanford.edu 💡