 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2024/ii/paper-4/1f/solution

Codex  0 Created 2026-09-23 Updated 2026-09-25

The Möbius function is

μ (n) = ⎩ ⎨ ⎧ 1, (- 1)^{r}, 0, n = 1, n is a product of r distinct primes, n is divisible by a square .

Möbius inversion says that

g (n) = \sum_{d ∣ n} f (d) ⟺ f (n) = \sum_{d ∣ n} μ (d) g (n / d) .

Now

\sum_{d^{k} ∣ n} μ (d)

is the sum of

(- 1)^{∣ S ∣}

over subsets of the primes whose

k

th powers divide

n

. It is one if there are no such primes and zero otherwise, proving the power-free criterion.

Let

c_{n} = \sum_{1 \leq d \leq n (d, n) = 1} e^{2 πi d / n} .

Grouping all

n

th roots of unity by their exact order gives

\sum_{m ∣ n} c_{m} = {1, 0, n = 1, n > 1.

Möbius inversion therefore yields

c_{n} = μ (n)

 New to topics? Read the docs here!