Paper 4, Section II, 7E7 \mathrm{E}

Numbers and Sets | Part IA, 2018

Let nNn \in \mathbb{N} and A1,,AnA_{1}, \ldots, A_{n} be subsets of a finite set XX. Let 0tn0 \leqslant t \leqslant n. Show that if xXx \in X belongs to AiA_{i} for exactly mm values of ii, then

S{1,,n}(St)(1)St1AS(x)={0 if mt1 if m=t\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 AS=iSAiA_{S}=\bigcap_{i \in S} A_{i} with the convention that A=XA_{\emptyset}=X, and 1AS\mathbf{1}_{A_{S}} denotes the indicator function of AS[A_{S} \cdot\left[\right. Hint: Set M={i:xAi}M=\left\{i: x \in A_{i}\right\} and consider for which S{1,,n}S \subset\{1, \ldots, n\} one has 1AS(x)=1\mathbf{1}_{A_{S}}(x)=1.]

Use this to show that the number of elements of XX that belong to AiA_{i} for exactly tt values of ii is

S{1,,n}(St)(1)StAS.\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 φ(N)\varphi(N) in terms of the distinct prime factors of NN.

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

Typos? Please submit corrections to this page on GitHub.