# Sums of squares of positive integers prime to n

• Nov 23rd 2009, 08:33 PM
ilikecandy
Sums of squares of positive integers prime to n
Let $\displaystyle S(n)$ denote the sum of the squares of the positive integers $\displaystyle \leq n$ and prime to $\displaystyle n$.
Prove that
$\displaystyle \sum_{j = 1}^n{j^2} = \sum_{d \mid n}{d^2S\left(\frac{n}{d}\right)} = \sum_{d \mid n}{\frac{n^2}{d^2}S(d)}$

I have trouble with separating the integers $\displaystyle \leq n$ into classes, so that all integers $\displaystyle k$ such that $\displaystyle (k,n) = d$ are in the same class.
Thanks for the help.
• Nov 23rd 2009, 11:15 PM
Shanks
Let $\displaystyle N=\{1^2,2^2,....n^2\}$, for each d|n, define $\displaystyle N_d=\{x^2:(x,n)=d\}$, then $\displaystyle \{N_d:d|n\}$ is a partion on N.
And for each $\displaystyle N_d$, Since $\displaystyle (\frac{x}{d},\frac{n}{d})=1$, By the definition of S(.), the sum of elements in $\displaystyle N_d$ is $\displaystyle d^2\times S(\frac{n}{d})$,
Thus,the first equality of$\displaystyle \sum_{j = 1}^n{j^2} = \sum_{d \mid n}{d^2S\left(\frac{n}{d}\right)} = \sum_{d \mid n}{\frac{n^2}{d^2}S(d)}$
is proved.
When d exhaust all the divisors of n, so do $\displaystyle \frac{n}{d}$, Thus the second equality obviously hold.