Past exam of the mathematics course of the University of Cambridge / 2018 / ia / Paper 4 / 7E / Solution

Let $M=\{i:x\in A_i\}$, with $|M|=m$. Then $1_{A_S}(x)=1$ exactly when $S\subseteq M$, and the sum becomesThis is $1$ when $m=t$ and $0$ otherwise. Summing over $x\in X$ yieldsTaking the complement of the $t=0$ case gives the inclusion-exclusion principle

If $p_1,\dots ,p_r$ are the distinct prime divisors of $N$, inclusion-exclusion removes their multiples from $\{1,\dots ,N\}$ and givesFor the stated squarefree $n=q_1\cdots q_k$ and $\gcd (x,n)=1$, Fermat's theorem gives $x^{q_j-1}\equiv 1(\mathrm{mod}{q}_j)$. Since $q_j-1\mid n-1$, every $q_j$ divides $x^{n-1}-1$; their product does too. Thus $n$ is a Carmichael number.