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