Let $n \in \mathbb{N}$ and $A_{1}, \ldots, A_{n}$ be subsets of a finite set $X$. Let $0 \leqslant t \leqslant n$. Show that if $x \in X$ belongs to $A_{i}$ for exactly $m$ values of $i$, then

$$\sum_{S \subset\{1, \ldots, n\}}\left(\begin{array}{c} |S| \\ t \end{array}\right)(-1)^{|S|-t} \mathbf{1}_{A_{S}}(x)= \begin{cases}0 & \text { if } m \neq t \\ 1 & \text { if } m=t\end{cases}$$

where $A_{S}=\bigcap_{i \in S} A_{i}$ with the convention that $A_{\emptyset}=X$, and $\mathbf{1}_{A_{S}}$ denotes the indicator function of $A_{S} \cdot\left[\right.$ Hint: Set $M=\left\{i: x \in A_{i}\right\}$ and consider for which $S \subset\{1, \ldots, n\}$ one has $\mathbf{1}_{A_{S}}(x)=1$.]

Use this to show that the number of elements of $X$ that belong to $A_{i}$ for exactly $t$ values of $i$ is

$$\sum_{S \subset\{1, \ldots, n\}}\left(\begin{array}{c} |S| \\ t \end{array}\right)(-1)^{|S|-t}\left|A_{S}\right| .$$

Deduce the Inclusion-Exclusion Principle.

Using the Inclusion-Exclusion Principle, prove a formula for the Euler totient function $\varphi(N)$ in terms of the distinct prime factors of $N$.

A Carmichael number is a composite number $n$ such that $x^{n-1} \equiv 1(\bmod n)$ for every integer $x$ coprime to $n$. Show that if $n=q_{1} q_{2} \ldots q_{k}$ is the product of $k \geqslant 2$ distinct primes $q_{1}, \ldots, q_{k}$ satisfying $q_{j}-1 \mid n-1$ for $j=1, \ldots, k$, then $n$ is a Carmichael number.