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

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

(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

Often this formula is rewritten as