Computing the Euler totient function, part 1

Recall that Euler’s totient function $\varphi(n)$ counts how many of the integers from $1$ to $n$ are relatively prime to $n$ , that is, share no factors in common with $n$ . For example, $\varphi(12) = 4$ , since only $1$ , $5$ , $7$ , and $11$ share no factors with $12$ ; on the other hand $\varphi(13) = 12$ , since every number from $1$ to $12$ shares no common factors with $13$ . We’ve encountered this function many times before, but I’ve never actually talked about how to compute it!

Of course, we could just count: that is, to compute $\varphi(n)$ , list all the numbers from $1$ to $n$ , and compute the GCD of each number with $n$ (using the Euclidean algorithm); count the ones for which the GCD is $1$ . This works, of course, but it is possible to compute $\varphi(n)$ much faster than this.

The key to computing $\varphi$ more quickly is that it is has the special property of being multiplicative: if $m$ and $n$ are relatively prime, then $\varphi(mn) = \varphi(m) \varphi(n)$ (don’t take my word for it though—we’ll prove it!).

Recall that we can break any number down as a product of distinct prime powers,

$n = p_1^{k_1} p_2^{k_2} \dots p_n^{k_n}.$

For example, $360 = 2^3 \cdot 3^2 \cdot 5^1$ . Of course, any powers of two different primes are relatively prime to each other (they are only divisible by their respective primes), so if $\varphi$ is multiplicative it means we can break down $\varphi(n)$ like this:

$\varphi(n) = \varphi(p_1^{k_1}) \varphi(p_2^{k_2}) \dots \varphi(p_n^{k_n}).$

Then all we have left to do is figure out how to compute $\varphi(p^k)$ for some power of a prime $p$ . That is, we’ve reduced a harder problem (“how many numbers are relatively prime to an arbitrary integer $n$ ?”) to a more specific and hopefully easier one (“how many numbers are relatively prime to an integer of the form $p^k$ for some prime number $p$ ?”). Some questions we still have to answer:

How do we know that $\varphi(mn) = \varphi(m) \varphi(n)$ when $m$ and $n$ are relatively prime? (Hint: look at my previous post and the one before that…)
How do we find $\varphi(p^k)$ ? You might like to try figuring this out too. As a warmup, what is $\varphi(p)$ ? Then what about $\varphi(p^2)$ ? Can you generalize?

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

View all posts by Brent →