MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


At for instance,, 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|cite|improve this question
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 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|cite|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.