## 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?