Hello,
At for instance, http://en.wikibooks.org/wiki/Famous_Theorems_of_Mathematics/Number_Theory/Totient_Function#Sum_of_integers_relatively_prime_to_and_less_than_or_equal_to_n,
there is a closed form for the integers relatively prime and less than an integer n, given by
$\displaystyle\sum_{1\leq n\leq k ,gcd(n,k)=1} n =\frac{k \varphi(k)}{2}$,
where $\varphi$ is the Euler totient function. I have spent days looking for a trick on how to write
$\displaystyle\sum_{1\leq n\leq k ,gcd(n,k)=1} n^2$
in some sort of closed form, which would reduce to the easily computed case when k is prime. I have had success in the past in finding closed forms for different sums, but this one keeps eluding me. Any ideas could be greatly appreciated
Best Answer
It's always a good idea to plug the first few terms into the OEIS. For 1,1,5,10,30,26, this leads to http://oeis.org/A053818 from which there's a reference to an exercise in Apostol's Introduction to Analytic Number Theory deriving the formula
$${1\over3}n^2\varphi(n) + {n\over6}\prod_{p|n}(1-p)$$
Added 11/12/12: I neglected to mention, the exercise in Apostol specifies the formula only applies for $n>1$. (Also, I had inadvertently switched, without saying so, from the OP's $k$ to Apostol's $n$.)