Past exam of the mathematics course of the University of Cambridge / 2004 / ia / Paper 4 / 8E (Numbers and Sets)

For each $x\in X$, the product ${\prod }_{i=1}^m(1-g_i(x))$ is $1$ precisely outside every $X_i$, and is $0$ otherwise. It is therefore the indicator function of $Y$. Expanding the finite product givesMultiply by $f(x)$ and sum over the finite set $X$. The product of indicator functions is the indicator function of the corresponding intersection, soHere the empty intersection is $X$, and the empty product is $1$. Grouping the subsets $S$ by their cardinality gives the requested weighted inclusion-exclusion principle, with no contribution for $r>m$.

Let $\mathcal{P}$ be the finite set of distinct prime factors of $n$, and work in $\{0,\dots ,n-1\}$. For $S\subseteq \mathcal{P}$ put $d_S={\prod }_{p\in S}p$, including $d_{\varnothing }=1$. Then $d_S\mid n$, and an integer belongs to every $X_p$ for $p\in S$ exactly when it is a multiple of $d_S$. Thus the intersection has size $n/d_S$. The complement consists precisely of the residues coprime to $n$. Using weight $1$ givesThis proves the product formula for the Euler totient function without requiring $n$ to be squarefree.

For the weight $f(x)=x$, the sum over the multiples of any divisor $d$ in this interval isThe weighted inclusion-exclusion principle therefore givesSince $n>1$, $\mathcal{P}$ is nonempty and the last sum is $(1-1{)}^{|\mathcal{P}|}=0$. The first factors as before, givingThis sum of reduced residues also follows by pairing the bijection $x\mapsto n-x$; at $n=2$ its sole fixed residue causes no problem because the sum of both copies still equals $n\phi (n)$.