Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm considering the following fun problem in number theory:

Let $n \in \mathbb{Z}$ with $n > 0$. If $k$ is a nonnegative integer, then $$\phi_k(n) = \sum_{1 \leq d \leq n, \, (d,n)=1} d^k.$$ Let $k$ be a nonnegative integer. Prove that $$\sum_{d \mid n} \frac{\phi_k(d)}{d^k} = \frac{1^k + 2^k + \cdots + n^k}{n^k}.$$

So my initial try so far has been to try to rewrite the sum: $$\sum_{d \mid n} \frac{\phi_k(d)}{d^k} = \sum_{d \mid n} \sum_{a \leq n, \, (a,n)=1} \left(\frac{a}{d}\right)^k = \sum_{d \mid n} \sum_{a \leq n} \sum_{b \mid (a,n)} \mu(b)\left(\frac{a}{d}\right)^k$$ using the summation over the Möbius function to write $1$ and then hoping for a simplification. But I can't seem to find one. Can you help me out?

share|cite|improve this question
up vote 2 down vote accepted

Start by observing that $$\sum_{q|n} \sum_{1\le d\le n, \;(d,n)=q} d^k = \sum_{p=1}^n p^k$$ because the left is merely a classification of $1\le p\le n$ according to the GCD of $p$ and $n$.

Now re-write the left as follows: $$\sum_{q|n} \sum_{1\le d/q\le n/q, \;(d/q,n/q)=1} d^k = \sum_{q|n} q^k \sum_{1\le d/q\le n/q, \; (d/q,n/q)=1} \left(\frac{d}{q}\right)^k \\= \sum_{q|n} q^k \phi_k(n/q) = \sum_{q|n} \phi_k(q) \left(\frac{n}{q}\right)^k = n^k \sum_{q|n} \frac{\phi_k(q)}{q^k}.$$ It follows that $$\sum_{q|n} \frac{\phi_k(q)}{q^k} = \frac{\sum_{p=1}^n p^k}{n^k} = \frac{1^k + 2^k + \cdots + n^k}{n^k}.$$

share|cite|improve this answer
Nice! I like it :) Thank you for your reply! Quick question: Why do you consider $d/q$ and $n/q$ and $(d/q,n/q)$ and not just $d$ and $n$? What is the idea in changing the first sum to a sum over $q$ instead of a sum over $d$? Also, could you explain the $\sum_{q \mid n} \sum_{1 \leq d \leq , \ (d,n)=q} d^k = \sum_{p=1}^n p^k$ equality? I can see that it is a classification, but it seems that the sum over the first n terms includes some terms not included in the first sum? – Numbersandsoon Oct 16 '13 at 0:37
Thank you. I'm sure you can answer these questions yourself and thereby understand the proof. For example, the equality at the top first partitions the numbers $p$ from the interval from $1$ to $n$ according to the GCD $q$ of $p$ and $n$, which must be a divisor of $n$. Every $p$ goes into exactly one partition and every $p$ is covered, so we get the sum of the $k$th powers of all $p.$ – Marko Riedel Oct 16 '13 at 0:50
There seems to be a typo in your problem statement where you put $k=2$ instead of a generic $k$ in your conjecture. – Marko Riedel Oct 16 '13 at 0:51

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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