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.

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: Logo

You are commenting using your 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.