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

  • 2
    $\begingroup$ 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$. $\endgroup$ Oct 25, 2015 at 3:36
  • 1
    $\begingroup$ 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? $\endgroup$ Oct 25, 2015 at 14:30
  • 1
    $\begingroup$ 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 $\endgroup$ Oct 25, 2015 at 20:42

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.