The Euler \phi Function

After reading the two previous sections, you're probably wondering why we stated the in such an abstract way, as in those examples \(N(S)\) depended only on the size of \(S\) and not its contents. In this section, we produce an important example where the value of \(N(S)\) does depend on \(S\). Nevertheless, we are able to make a reduction to obtain a useful end result. In what follows, let \(\posints\) denote the set of positive integers.

For a positive integer \(n\ge2\), let \[\begin{aligned}\end{aligned}\] This function is usually called the Euler \(\phi\) function or the Euler totient function and has many connections to number theory. We won't focus on the number-theoretic aspects here, only being able to compute \(\phi(n)\) efficiently for any \(n\).\(\phi(n)\)Euler \(\phi\) function

For example, \(\phi(12)=4\) since the only numbers from \(\{1,2,\dots,12\}\) that are relatively prime to \(12\) are \(1\), \(5\), \(7\) and \(11\). As a second example, \(\phi(9)=6\) since \(1\), \(2\), \(4\), \(5\), \(7\) and \(8\) are relatively prime to \(9\). On the other hand, \(\phi(p)=p-1\) when \(p\) is a prime. Suppose you were asked to compute \(\phi(321974)\). How would you proceed?

In we discussed a recursive procedure for determining the greatest common divisor of two integers, and we wrote code for accomplishing this task. Let's assume that we have a function gcd(m,n) that returns the greatest common divisor of the integers m and n. (Conveniently enough, SageMath comes such a function built in.) Then we can calculate \(\phi(n)\) with this code snippet:

Running the code above answers almost immediately that \(\phi(321974) = 147744\). (As usual, in the web version of the text, you can change the value 321974 to calculate the value of \(\phi\) for other integers. However, if you try to increase the value of n to be too large, you may run into memory issues imposed by the Sage Cell Server used by the text. For instance, attempting to calculate \(\phi(319572943)\) results in an error at the time of writing. (You may have better luck running the code directly in the CoCalc or a local installation of SageMath.)

Given these difficulties, how could we find \(\phi(1369122257328767073)\)?

Clearly, the program is useless to tackle this beast! It not only iterates \(n-2\) times but also invokes a recursion during each iteration. Fortunately, Inclusion-Exclusion comes to the rescue.

Our proof of requires the following elementary proposition whose proof we leave as an exercise.

Condensed — the full section is in Keller & Trotter, Applied Combinatorics.