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:

  1. 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…)

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

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.

1 Response to Computing the Euler totient function, part 1

  1. Pingback: Computing the Euler totient function, part 4: totient of prime powers | The Math Less Traveled

Comments are closed.