Recall that Euler’s totient function counts how many of the integers from to are relatively prime to , that is, share no factors in common with . For example, , since only , , , and share no factors with ; on the other hand , since every number from to shares no common factors with . 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 , list all the numbers from to , and compute the GCD of each number with (using the Euclidean algorithm); count the ones for which the GCD is . This works, of course, but it is possible to compute much faster than this.
The key to computing more quickly is that it is has the special property of being multiplicative: if and are relatively prime, then (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,
For example, . Of course, any powers of two different primes are relatively prime to each other (they are only divisible by their respective primes), so if is multiplicative it means we can break down like this:
Then all we have left to do is figure out how to compute for some power of a prime . That is, we’ve reduced a harder problem (“how many numbers are relatively prime to an arbitrary integer ?”) to a more specific and hopefully easier one (“how many numbers are relatively prime to an integer of the form for some prime number ?”). Some questions we still have to answer:
How do we know that when and are relatively prime? (Hint: look at my previous post and the one before that…)
How do we find ? You might like to try figuring this out too. As a warmup, what is ? Then what about ? Can you generalize?
Pingback: Computing the Euler totient function, part 4: totient of prime powers | The Math Less Traveled