# Show that $\sum_{d \mid n} \frac{\phi_k(d)}{d^k}=\frac{1^k +2^k + \cdots + n^k}{n^k}$

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?

-

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}.$$
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