Section 7.5 The Euler \(\phi\) Function
After reading the two previous sections, you're probably wondering why we stated the Principle of Inclusion-Exclusion 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\text{.}\) 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\text{,}\) let
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\text{.}\)
For example, \(\phi(12)=4\) since the only numbers from \(\{1,2,\dots,12\}\) that are relatively prime to \(12\) are \(1\text{,}\) \(5\text{,}\) \(7\) and \(11\text{.}\) As a second example, \(\phi(9)=6\) since \(1\text{,}\) \(2\text{,}\) \(4\text{,}\) \(5\text{,}\) \(7\) and \(8\) are relatively prime to \(9\text{.}\) On the other hand, \(\phi(p)=p-1\) when \(p\) is a prime. Suppose you were asked to compute \(\phi(321974)\text{.}\) How would you proceed?
In Chapter 3 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\text{.}\) (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 1 or a local installation of SageMath.)
Given these difficulties, how could we find \(\phi(1369122257328767073)\text{?}\)
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.
Theorem 7.14.
Let \(n\ge2\) be a positive integer and suppose that \(n\) has \(m\) distinct prime factors: \(p_1\text{,}\) \(p_2,\dots,p_m\text{.}\) Then
Our proof of Theorem 7.14 requires the following elementary proposition whose proof we leave as an exercise.
Proposition 7.15.
Let \(n\ge2\text{,}\) \(k\ge1\text{,}\) and let \(p_1,p_2,\dots,p_k\) be distinct primes each of which divide \(n\) evenly (without remainder). Then the number of integers from \(\{1,2,\dots,n\}\) which are divisible by each of these \(k\) primes is
Proof.
We present the argument when \(m=3\text{.}\) The full result is an easy extension.
In light of Proposition 7.15, the Principle of Inclusion-Exclusion yields:
Example 7.16.
SageMath reports that
is the factorization of \(1369122257328767073\) into primes. It follows that
Thus SageMath quickly reports that
Example 7.17.
Amanda and Bruce receive the same challenge from their professor, namely to find \(\phi(n)\) when
However the Professor also tells Amanda that \(n=p_1p_2\) is the product of two large primes where
and
\begin{align*} p_2 \amp = 669483106578092405936560831017556154622901950048903016651289. \end{align*}Is this information of any special value to Amanda? Does it really make her job any easier than Bruce's? Would it level the playing field if the professor told Bruce that \(n\) was the product of two primes?
cocalc.com