# inclusion-exclusion principle - challenging problem [closed]

I wonder how to write proper solution to the following problem given below:

Let $$\mathbb{N}$$ be the set of all positive integers. Let a map $$f:\mathbb{N}\to \mathbb{N}$$ be defined in the following way:

• $$f(n)$$ is the number of positive integers $$i$$ that are relatively prime to given $$n$$ and satisfy $$i \leq n$$.

By the use of inclusion-exclusion principle, derive formula for the function $$f(n)$$.

Any help very appreciated!

I know that $$f$$ is called Euler's totient function.

Your $$f\left(n\right)$$ is $$\varphi(n)$$, where $$\varphi$$ is Euler's totient function. Here is the formula you want to prove:

$$\varphi(n)= n\prod_{\substack{p \text{ prime }\ p \vert n}} \left( 1- \frac{1}{p}\right)$$

Let's prove why it is the quantity you want. We will assume that we know that the totient function is multiplicative (if $$a$$ and $$b$$ are coprime then $$\varphi(ab)=\varphi(a) \varphi(b)$$).

Also $$\varphi(p^k)=p^k-p^{k-1}=p^k(1-\frac{1}{p})$$, indeed the only way for an integer $$m$$ to not be comprime with $$p^k$$ is to be a multiple of $$p$$. The multiples of $$p$$ which are $$\le p^k$$ are $$p,2p,3p,...,p^k(=p^{k-1}p)$$, so there are $$p^{k-1}$$ of them. So the $$p^k-p^{k-1}$$ remaining numbers are coprime with $$p^k$$.

By the fundamental theorem of arithmetic there is a unique decomposition for $$n$$ in product of primes numbers : $$n=p_1^{a_1}p_2^{a_2}...p_k^{a_k}$$. Thus we have : $$\varphi(n)=\varphi(p_1^{a_1})\varphi(p_2^{a_2})...\varphi(p_k^{a_k})$$ $$\varphi(n)=p_1^{a_1}p_2^{a_2}...p_k^{a_k}( 1- \frac{1}{p_1})( 1- \frac{1}{p_2})...( 1- \frac{1}{p_k})$$ $$\varphi(n)=n( 1- \frac{1}{p_1})( 1- \frac{1}{p_2})...( 1- \frac{1}{p_k})$$ We obtain the formula stated before.

A combinatorial proof now.

First we have the following identity : \begin{aligned} \prod_{i=1}^n (1 - x_i) &= 1 - \sum_{i=1}^n x_i + \sum_{i,j=1}^n x_i x_j - \sum_{i,j,k=1}^n x_i x_j x_k + \cdots + (-1)^n x_1 x_2 \cdots x_n \\ & = \sum_{I \subset {1, 2, \ldots, n}} (-1)^{|I|}\prod_{i \in I} x_i \end{aligned}

How are we going to apply the inclusion-exclusion principle ?

For a positive integer $$n$$, whenever you divide $$n$$ by one of its prime factors $$p$$, you obtain then number of positive integers $$\le n$$ which are a multiple of $$p$$, so all of these numbers are not coprime with $$n$$. But when you consider the numbers which are multiple of $$p_1$$ or $$p_2$$, if you want to count them you have to compute $$\frac{n}{p_1}+\frac{n}{p_2}-\frac{n}{p_1p_2}$$, you substract the number of integers which are in the same time a multiple of $$p_1$$ and $$p_2$$. Following this reasonning we have :

\begin{aligned} \varphi(n) &= n - \sum_{\substack{p_i \text{ prime }\ p_i \vert n}} \frac{n}{p_i} + \sum_{\substack{p_i,p_j \text{ prime }\ p_i,p_j \vert n}} \frac{n}{p_i p_j} -\sum_{\substack{p_i,p_j,p_k \text{ prime }\ p_i,p_j,p_k \vert n}} \frac{n}{p_i p_j p_k} + \cdots + (-1)^{|Pr|} \frac{n}{p_1 p_2 \cdots p} \\\\ &= n \left(1 - \sum \frac{1}{p_i} + \sum \frac{1}{p_i p_j} -\sum \frac{1}{p_i p_j p_k} + \cdots + (-1)^{|Pr|} \frac{1}{p_1 p_2 \cdots p } \right) \\\\ &= n \prod_{p \in Pr} \left(1-\frac{1}{p}\right) \end{aligned}

Where $$Pr$$ is the set of the primes which divide $$n$$. The last equality is obtained thanks to the identity proved before.

For each prime $p$ so that $p\mid n$, the number of integers less than or equal to $n$ that share a factor of $p$ with $n$ is $\frac np$

For each pair of primes $p_1,p_2$, the number of integers less than or equal to $n$ that share a factors of $p_1$ and $p_2$ with $n$ is $\frac n{p_1p_2}$

For each triple of primes $p_1,p_2,p_3$, the number of integers less than or equal to $n$ that share a factors of $p_1$, $p_2$, and $p_3$ with $n$ is $\frac n{p_1p_2p_3}$.

And so forth.

Therefore, using Inclusion-Exclusion, the number of integers less than or equal to $n$ that share a prime factor with $n$ would be $$\sum_{p\mid n}\frac np-\sum_{p_1\lt p_2\mid n}\frac n{p_1p_2}+\sum_{p_1\lt p_2\lt p_3\mid n}\frac n{p_1p_2p_3}-\dots$$ Thus, the number of integers less than $n$ that share no prime factors with $n$ is \begin{align} &n-\sum_{p\mid n}\frac np+\sum_{p_1\lt p_2\mid n}\frac n{p_1p_2}-\sum_{p_1\lt p_2\lt p_3\mid n}\frac n{p_1p_2p_3}+\dots\\ &=n\left(1-\sum_{p\mid n}\frac1p+\sum_{p_1\lt p_2\mid n}\frac1{p_1p_2}-\sum_{p_1\lt p_2\lt p_3\mid n}\frac1{p_1p_2p_3}+\dots\right)\\[6pt] &=n\prod_{p\mid n}\left(1-\frac1p\right) \end{align}

• Hi! I am not able to prove the last identity, how do you prove sum of those sigma values is equal to that continued product? May 21, 2017 at 12:14
• @ash: list out all the $\left(1-\frac1{p_i}\right)$ in order of increasing $p_i$. The terms of first order are $-\sum\limits_{p\mid n}\frac np$. The terms of second order are $\sum\limits_{p_1\lt p_2\mid n}\frac n{p_1p_2}$. etc.
– robjohn
May 21, 2017 at 18:21