Take the 2-minute tour ×


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 14 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


