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.

Solution

Past exam of the mathematics course of the University of Cambridge / 2025 / iii / Paper 150 / 1 / a / Solution

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2025/iii/paper-150/1/a/solution