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


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


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.