## Section7.5The 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 SageMath Cloud 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.

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*}
###### Example7.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*}
###### Example7.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?