# power sums and formal divisibility by the Euler totient function

For integers $s \geq 0$ and $n \geq 1$ let $\sigma_s(n) := 1^s + \dots + n^s$ and let

\begin{equation} \sigma_s^*(n) \ : = \ \sum_{\stackrel{\scriptstyle 1 \, \leq \, m \, \leq \, n}{\text{gcd}(m,n) = 1}} m^s \end{equation}

It is not to difficult to check that $\sigma^*$ can be expressed as the Dirichlet convolution $\big( \mu \cdot \Bbb{i}^s \big) * \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 $\big( \mu \cdot \Bbb{i}^s \big)(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$ formula for $\sigma_s^*(n)$ with $n > 1$ are given by

\begin{equation} \begin{array} $\phi(n) &\text{when} \quad s = 0 \\ \\ \Big( 1 \over \displaystyle 2} \,n \Big) \, \phi(n) &\text{when} \quad s=1 \\ \\ \Big( 1 \over \displaystyle 3 } \, n^2 + 1 \over \displaystyle 6} \, \mu\big(\text{rad}(n) \big) \, \text{rad}(n)\Big) \, \phi(n) &\text{when} \quad s=2 \end{array} \end{equation} Where$\phi$is the Euler totient function and$\text{rad}(n)$denotes the radical of the integer$n$.${ \bf \text{Question}}$: Is$\sigma_s^*$always "formally" divisible by$\phi$for any integer$s \geq 0$? • You mean divisible "as formal expressions" in some sense, as opposed to as integers? Because$\dfrac{1}{2}n$isn't exactly an integer for odd$n$. – darij grinberg Oct 25 '15 at 3:36 • I believe that the formulas for the cases$s=1,2$miss the term$\frac{1}{2}\delta_{n,1}$, as they are not valid for$n=1$. According to the calculations in my answer,$\mu(n)$in the case$s=2$should be replaced with$\mu(\text{rad}(n))$. What is the text of Vinogradov you are talking about? – Ofir Gorodetsky Oct 25 '15 at 14:30 • A somewhat poor english translation of Vinogradov's "An introduction to the theory of numbers"; exercise 18 from the chapter on "fundamental functions". best, Ines – Ines Institoris Oct 25 '15 at 20:42 ## 1 Answer 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. 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.