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, , counts how many numbers from to are relatively prime to (that is, share no prime factors in common with) .
My current goal is to show that if we know the prime factorization of , we can calculate much more quickly than just by counting.
This rests on the fact that is multiplicative, that is, whenever and are relatively prime. In particular this means we can break down based on a number’s prime factorization:
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 . That’s what we’ll do today! Then we’ll see the whole method of computing in action.
Totient of prime powers
As a warmup, what is when is prime? Since 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 to is relatively prime to , and .
How about ? Here’s an example with . The blue squares are the numbers relatively prime to —the ones we want to count—and the white squares are the ones which share a prime factor with .
In general, the only numbers that share a prime factor with are numbers that are divisible by . In the example above, there are five white squares; in general, counting itself, there are exactly of these numbers: . So all of the numbers from to are relatively prime to except for those multiples of , for a total of . Put another way, exactly one out of every numbers is divisible by , so each consecutive group of numbers yields which are relatively prime to . There are such groups up to , so the total is . In the example with , you can verify that there are blue squares.
Finally, what about bigger powers, ? Well, once again, the only numbers which share any common factor with are exactly the multiples of . There’s one multiple of (and non-multiples of ) in every group of numbers. How many such groups are there up to ? There are of them. Hence .
Putting it all together
A previous post contained an example that required computing ; now we can see how to do it. First, we factor the number as . Then, using the fact that is multiplicative, we can break it down into three separate applications of :
Finally, we can evaluate for each of these prime powers:
Hence . 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