Computing the Euler totient function, part 4: totient of prime powers

I’ve been on a bit of a hiatus as I’ve been travelling with my family for the past month. So here’s a recap.

Our story so far

Recall that the Euler totient function, $\varphi(n)$ , counts how many numbers from $1$ to $n$ are relatively prime to (that is, share no prime factors in common with) $n$ .
My current goal is to show that if we know the prime factorization of $n$ , we can calculate $\varphi(n)$ much more quickly than just by counting.
This rests on the fact that $\varphi$ is multiplicative, that is, $\varphi(mn) = \varphi(m)\varphi(n)$ whenever $m$ and $n$ are relatively prime. In particular this means we can break down $\varphi$ based on a number’s prime factorization: $\varphi(p_1^{k_1} p_2^{k_2} \dots p_n^{k_n}) = \varphi(p_1^{k_1}) \varphi(p_2^{k_2}) \dots \varphi(p_n^{k_n}).$
First I displayed some visualizations that give us some intuition for why this is true. Then in another post I presented a formal proof based on that intuition.
So the only thing left is to figure out how to compute $\varphi(p^k)$ . That’s what we’ll do today! Then we’ll see the whole method of computing $\varphi$ in action.

Totient of prime powers

As a warmup, what is $\varphi(p)$ when $p$ is prime? Since $p$ is prime, by definition it has no prime factors other than itself, and no smaller number can share a prime factor with it. Hence every number from $1$ to $p-1$ is relatively prime to $p$ , and $\varphi(p) = p-1$ .

How about $\varphi(p^2)$ ? Here’s an example with $p=5$ . The blue squares are the numbers relatively prime to $5^2 = 25$ —the ones we want to count—and the white squares are the ones which share a prime factor with $25$ .

In general, the only numbers that share a prime factor with $p^2$ are numbers that are divisible by $p$ . In the example above, there are five white squares; in general, counting $p^2$ itself, there are exactly $p$ of these numbers: $p, 2p, 3p, 4p, \dots, (p-1)p, p^2$ . So all of the numbers from $1$ to $p^2$ are relatively prime to $p^2$ except for those $p$ multiples of $p$ , for a total of $p^2 - p$ . Put another way, exactly one out of every $p$ numbers is divisible by $p$ , so each consecutive group of $p$ numbers yields $p-1$ which are relatively prime to $p$ . There are $p$ such groups up to $p^2$ , so the total is $p(p-1) = p^2 - p$ . In the example with $p=5$ , you can verify that there are $5^2 - 5 = 5 \cdot (5-1) = 20$ blue squares.

Finally, what about bigger powers, $\varphi(p^k)$ ? Well, once again, the only numbers which share any common factor with $p^k$ are exactly the multiples of $p$ . There’s one multiple of $p$ (and $p-1$ non-multiples of $p$ ) in every group of $p$ numbers. How many such groups are there up to $p^k$ ? There are $p^{k-1}$ of them. Hence $\varphi(p^k) = p^{k-1}(p-1)$ .

Putting it all together

A previous post contained an example that required computing $\varphi(151389)$ ; now we can see how to do it. First, we factor the number as $151389 = 3^5 \cdot 7 \cdot 89$ . Then, using the fact that $\varphi$ is multiplicative, we can break it down into three separate applications of $\varphi$ :

$\varphi(3^5 \cdot 7 \cdot 89) = \varphi(3^5) \cdot \varphi(7) \cdot \varphi(89)$ .

Finally, we can evaluate $\varphi$ for each of these prime powers:

$\varphi(3^5) = 3^4 \cdot (3-1) = 81 \cdot 2 = 162$
$\varphi(7) = 6$
$\varphi(89) = 88$

Hence $\varphi(151389) = 162 \cdot 6 \cdot 88 = 85536$ . For this relatively small number we can actually double-check this result using a computer to count the answer by brute force:

>>> length [n | n <- [1 .. 151389], gcd n 151389 == 1]
85536

Math works!

About Brent

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

View all posts by Brent →