# 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 + \dotsb + n^s$$ and let

$$$$\sigma_s^*(n) \ : = \ \sum_{\substack{\scriptstyle 1 \, \leq \, m \, \leq \, n \\ \gcd(m,n) = 1}} m^s.$$$$

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$$ ?

• 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$. Oct 25, 2015 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? Oct 25, 2015 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 Oct 25, 2015 at 20:42

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.