For integers $s \geq 0$ and $n \geq 1$ let $\sigma\_s(n) := 1^s + \dotsb + n^s$ and let


\begin{equation} \sigma\_s^\*(n) \ : = \ \sum\_{\substack{\scriptstyle 1 \, \leq \, m \, \leq \, n \\ \gcd(m,n) = 1}} m^s. \end{equation}


It is not to difficult to check that $\sigma^\*$ can be expressed
as the Dirichlet convolution $\bigl( \mu \cdot \Bbb{i}^s \bigr) \* \sigma\_s$
where $\mu$ is the Möbius funtion, $\Bbb{i}$ is the identity function, namely $\Bbb{i}(n) = n$ for all integers $n \geq 1$, and
$\mu \cdot \Bbb{i}^s$ is the point-wise product, namely $\bigl( \mu \cdot
\Bbb{i}^s \bigr)(n) = \mu(n) \, n^s$ for all integers $n \geq 1$.
A cute little exercise in Vinogradov's text asserts that when $s=0, 1, 2$
formulas for $\sigma\_s^\*(n)$ with $n > 1$ are given by


\begin{align\*}
&\phi(n) &\text{when} \quad s = 0 \\ \\
&\Bigl( {\displaystyle 1 \over 2} \,n \Bigr) \, \phi(n) &\text{when} \quad s=1 \\ \\ 
& \Bigl( {\displaystyle 1 \over 3 } \, n^2 + {\displaystyle 1 \over 6} \, \mu\bigl(\operatorname{rad}(n) \bigr) \, \operatorname{rad}(n)\Bigr) \, \phi(n) &\text{when} \quad s=2 
\end{align\*}


where $\phi$ is the Euler totient function and $\operatorname{rad}(n)$ denotes the
radical of the integer $n$.


**Question**: Is $\sigma\_s^\*$ always "formally" divisible by $\phi$ for any integer $s \geq 0$ ?



Power sums and formal divisibility by the Euler totient function
Nice question. The answer is positive. I will give a very constructive answer.


First, write $\sigma\_s(n)$ as a polynomial in $n$ of degree $s+1$: 
$$\sigma\_s(n) = \sum a\_i n^i$$
The numbers $a\_i$ are closely related to Bernoulli numbers, see this [Wikipedia page](https://en.wikipedia.org/wiki/Faulhaber%27s_formula). In particular, $a\_0=0,a\_{s}=\frac{1}{2}, a\_{s+1}=\frac{1}{s+1}$.


By the convolution identity relating $\sigma\_s^{\*}(n)$ to $\sigma\_s(n)$ via the Möbius function, we find:


$$\sigma\_s^{\*}(n) = \sum\_{i} a\_i \sum\_{d \mid n} (\frac{n}{d})^i\mu(d)d^s$$


It is enough to demonstrate that $\frac{\sum\_{d \mid n}(\frac{n}{d})^i\mu(d)d^s }{\phi(n)}$ has some "nice" expression for any $i\le s+1$. Since $n \mapsto n^i, n\mapsto \mu(n) n^s$ are multiplicative functions, this numerator is a multiplicative function of $n$ and so is the ratio itself. We will evaluate it on the prime power $p^k$ ($k>0$):


If $i=s+1$ we get $(p^k)^s$, and so by multiplicativity, $\frac{\sum\_{d \mid n}(\frac{n}{d})^i\mu(d)d^s }{\phi(n)}=n^s$.


If $i=s$ we get $0$ ($\sum\_{d \mid p^k} \mu(d)=0$), and so by multiplicativity, $\frac{\sum\_{d \mid n}(\frac{n}{d})^i\mu(d)d^s }{\phi(n)}=\delta\_{n,1}$.


If $i<s$ we get
$$\frac{\sum\_{d \mid p^k}(\frac{p^k}{d})^i\mu(d)d^s }{\phi(p^k)} = (-p) \cdot (p^k)^{i-1} (1+p+p^2+\cdots+p^{s-i-1}).$$
By multiplicativity, $\frac{\sum\_{d \mid n}(\frac{n}{d})^i\mu(d)d^s }{\phi(n)}=\text{rad}(n) \mu(\text{rad}(n))n^{i-1} \cdot \sigma(\text{rad}^{s-i-1}(n))$, where $\sigma$ is the sum-of-divisors function.


This settles your problem.


