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]

Math works!

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in arithmetic, computation, counting and tagged , , . Bookmark the permalink.