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.

Solution 1:

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.

Solution 2:

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} $$