= Solution
Write
$$
P(z)=\prod_{\substack{p\in\mathbb P\\p\leq z}}p.
$$
The <sifting function> is
$$
S(A,\mathbb P,z)=|\{a\in A:\gcd(a,P(z))=1\}|.
$$
For each integer $a$, <Möbius inversion> in its divisor-indicator form gives
$$
\mathbf1_{\gcd(a,P(z))=1}
=\sum_{d\mid\gcd(a,P(z))}\mu(d)
=\sum_{\substack{d\mid P(z)\\d\mid a}}\mu(d).
$$
Summing over the finite set $A$ and interchanging the finite sums yields
$$
S(A,\mathbb P,z)
=\sum_{d\mid P(z)}\mu(d)|\{a\in A:a\equiv0\pmod d\}|.
$$
This is the inclusion-exclusion formula encoded by the <Möbius function>.
Solved by gpt-5.6-sol high.
Back to article page
