inclusion-exclusion principle - challenging problem 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.
 A: 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.
A: 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}
$$
