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
\begin{equation}
\phi(n) = n\prod_{i = 1}^{m}\frac{p_i-1}{p_i}.\tag{7.5.1}
\end{equation}
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
\begin{equation*}
\phi(n)=|\{m\in \posints: m\le n, \gcd(m,n)=1\}|.
\end{equation*}
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.
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
\begin{equation*}
\frac{n}{p_1p_2\dots p_k}.
\end{equation*}
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:
\begin{align*}
\phi(n) \amp = n-\left(\frac{n}{p_1}+\frac{n}{p_2}+
\frac{n}{p_3}\right) +\left(\frac{n}{p_1p_2}+\frac{n}{p_1p_3}+
\frac{n}{p_2p_3}\right)-\frac{n}{p_1p_2p_3}\\
\amp = n \frac{p_1p_2p_3 -(p_2p_3+p_1p_3+p_1p_2)+
(p_3+p_2+p_1) - 1}{p_1p_2p_3}\\
\amp =n \frac{p_1-1}{p_1}\frac{p_2-1}{p_2}
\frac{p_3-1}{p_3}.
\end{align*}
Example 7.16.
SageMath reports that
\begin{equation*}
1369122257328767073 = (3)^3(11)(19)^4(31)^2(6067)^2
\end{equation*}
is the factorization of \(1369122257328767073\) into primes. It follows that
\begin{equation*}
\phi(1369122257328767073) = 1369122257328767073
\,\,\frac{2}{3}\,\frac{10}{11}\,\frac{18}{19}\,\frac{30}{31}\,\frac{6066}{6067}.
\end{equation*}
Thus SageMath quickly reports that
\begin{equation*}
\phi(1369122257328767073) =760615484618973600.
\end{equation*}
Example 7.17.
Amanda and Bruce receive the same challenge from their professor, namely to find \(\phi(n)\) when
\begin{align*}
n = \amp 31484972786199768889479107860964368171543984609017931\\
\amp 39001922159851668531040708539722329324902813359241016\\
\amp 93211209710523.
\end{align*}
However the Professor also tells Amanda that \(n=p_1p_2\) is the product of two large primes where
\begin{align*}
p_1 \amp = 470287785858076441566723507866751092927015824834881906763507\\
\end{align*}
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
