I'm doing an excercise in Alan Baker's book A Concise Introduction to the Theory of Numbers, and I'm confused about the method spelled out for one question. I'll quote it here:
Let $a$ run through all the integers with $1\leq a\leq n$ and $(a,n)=1$. Show that $f(n)=\frac1n\sum a$ satisfies $\sum_{d|n}f(d)=\frac12(n+1)$. Hence prove that $f(n)=\frac12\phi(n)$ for $n>1$.
My issue is this: I can prove the end result, but not using the intermediate step suggested. It's just clear that $2f(n)=\phi(n)$, because $n-a$ runs through all the same values as $a$ (assuming $n>1$), so you get $\phi(n)$ copies of $n$, and then divide by $n$. I can then use that fact to prove the suggested intermediate step about summing $f(d)$ over the divisors.
It seems that I'm not doing what the exercise suggests. Does anyone see how the author intended for this problem to be done? Is there some nice combinatorial argument or something for the formula $\sum_{d|n}f(d)=\frac12(n+1)$ that I'm just not seeing?
Thanks in advance.
Honestly, I think your proof is nicer than the one the book intended. We can rewrite the sum $$ f(d) = \frac{1}{d} \sum_{(d,a) = 1} a = \sum_{(d,a) = 1} \frac{a\cdot(n/d)}{n} $$ Now note that as $a$ ranges across the values $\le d$ relatively prime to $d$, $(n/d)a$ ranges across the values $i\le n$ satisfying $(i,n) = n/d$. We now can compute $$ \frac{n+1}{2} = \frac{n^2+n}{2n} = \sum_{i=1}^n \frac{i}{n} = \sum_{d\mid n} \sum_{(i,n) = n/d}\frac{i}{n} = \sum_{d\mid n} \sum_{(d,a) = 1} \frac{a\cdot(n/d)}{n} = \sum_{d\mid n} f(d) $$ You then get $f(n) = \phi(n)/2$ for $n>1$ through Möbius inversion, as mentioned in comments.