Sum of integers squared relatively prime to and less than n ??? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-26T04:27:08Z http://mathoverflow.net/feeds/question/112113 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/112113/sum-of-integers-squared-relatively-prime-to-and-less-than-n Sum of integers squared relatively prime to and less than n ??? Nathan 2012-11-11T21:37:51Z 2012-11-12T12:46:42Z <p>Hello,</p> <p>At for instance, <a href="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" rel="nofollow">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</a>, 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}$,</p> <p>where $\varphi$ is the Euler totient function. I have spent days looking for a trick on how to write</p> <p>$\displaystyle\sum_{1\leq n\leq k ,gcd(n,k)=1} n^2$ </p> <p>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</p> http://mathoverflow.net/questions/112113/sum-of-integers-squared-relatively-prime-to-and-less-than-n/112115#112115 Answer by Barry Cipra for Sum of integers squared relatively prime to and less than n ??? Barry Cipra 2012-11-11T22:00:01Z 2012-11-12T12:46:42Z <p>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 <a href="http://oeis.org/A053818" rel="nofollow">http://oeis.org/A053818</a> from which there's a reference to an exercise in Apostol's <em>Introduction to Analytic Number Theory</em> deriving the formula</p> <p>$${1\over3}n^2\varphi(n) + {n\over6}\prod_{p|n}(1-p)$$</p> <p><strong>Added 11/12/12:</strong> 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$.)</p>