Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.


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

share|improve this question

1 Answer 1

up vote 13 down vote accepted

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

share|improve this answer

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.