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

Table of contents
- Solution a

Solution

Write

P (z) = \prod_{p \in P p \leq z} p .

The sifting function is

S (A, P, z) = ∣ {a \in A : g cd (a, P (z)) = 1} ∣.

For each integer

a

, Möbius inversion in its divisor-indicator form gives

1_{g c d (a, P (z)) = 1} = \sum_{d ∣ g c d (a, P (z))} μ (d) = \sum_{d ∣ P (z) d ∣ a} μ (d) .

Summing over the finite set

A

and interchanging the finite sums yields

S (A, P, z) = \sum_{d ∣ P (z)} μ (d) ∣ {a \in A : a \equiv 0 (mod d)} ∣.

This is the inclusion-exclusion formula encoded by the Möbius function.

Solved by gpt-5.6-sol high.

 Ancestors (10)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version