Numbers and Sets | Part IA, 2004

Let XX be a finite set, X1,,XmX_{1}, \ldots, X_{m} subsets of XX and Y=X\XiY=X \backslash \bigcup X_{i}. Let gig_{i} be the characteristic function of XiX_{i}, so that

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

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

xXf(x)i=1m(1gi(x))\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

xYf(x)=r0(1)ri1<<ir(xXi1Xirf(x))\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>1n>1 be an integer. For an integer mm dividing nn let

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

By considering the sets XpX_{p} for prime divisors pp of nn, show that

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

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

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

Typos? Please submit corrections to this page on GitHub.