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

Assistant 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.

Leave a reply. You can include LaTeX $latex like this$. Note you have to literally write 'latex' after the first dollar sign!

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.