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.