Let $X$ be a finite set, $X_{1}, \ldots, X_{m}$ subsets of $X$ and $Y=X \backslash \bigcup X_{i}$. Let $g_{i}$ be the characteristic function of $X_{i}$, so that

$$g_{i}(x)= \begin{cases}1 & \text { if } x \in X_{i} \\ 0 & \text { otherwise }\end{cases}$$

Let $f: X \rightarrow \mathbb{R}$ be any function. By considering the expression

$$\sum_{x \in X} f(x) \prod_{i=1}^{m}\left(1-g_{i}(x)\right)$$

or otherwise, prove the Inclusion-Exclusion Principle in the form

$$\sum_{x \in Y} f(x)=\sum_{r \geq 0}(-1)^{r} \sum_{i_{1}<\cdots<i_{r}}\left(\sum_{x \in X_{i_{1}} \cap \cdots \cap X_{i_{r}}} f(x)\right)$$

Let $n>1$ be an integer. For an integer $m$ dividing $n$ let

$$X_{m}=\{0 \leq x<n \mid x \equiv 0(\bmod m)\}$$

By considering the sets $X_{p}$ for prime divisors $p$ of $n$, show that

$$\phi(n)=n \prod_{p \mid n}\left(1-\frac{1}{p}\right)$$

(where $\phi$ is Euler's function) and

$$\sum_{\substack{0<x<n \\(x, n)=1}} x=\frac{n^{2}}{2} \prod_{p \mid n}\left(1-\frac{1}{p}\right) .$$