Let n=p1e1…pkekn = p_1^{e_1} \dots p_k^{e_k}n=p1e1…pkek. What is the sum of gcd(i,n)\text{gcd}(i, n)gcd(i,n) for i=1…ni=1 \dots ni=1…n?
∑d∣ndϕ(n/d)\sum_{d|n} d \phi(n/d)∑d∣ndϕ(n/d)
ϕ(n)\phi(n)ϕ(n)
n(n+1)2\frac{n(n+1)}{2}2n(n+1)
n⋅2kn \cdot 2^kn⋅2k