## 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! 