How to prove $ \sum_{k=1}^{p-1}\left\lfloor \frac{k^3}{p}\right\rfloor=\frac{(p-2)(p-1)(p+1)}4 $? Equation $(36)$ at Mathworld's Prim Sums page reads:
$$
\sum_{k=1}^{p-1}\left\lfloor \frac{k^3}{p}\right\rfloor=\frac{(p-2)(p-1)(p+1)}4
$$
I'm curious how this can be proven, but I have no idea...
 A: The idea is surely to compare the two sums
$$
A=\sum_{k=1}^{p-1}\frac{k^3}p\qquad\text{and}\qquad B=\sum_{k=1}^{p-1}\left\lfloor\frac{k^3}p\right\rfloor.
$$
We see that the difference $A-B$ equals the sum of least positive remainders of the cubes $k^3$ modulo $p$ divided by $p$. 
I claim that the sum of those remainders is $p(p-1)/2$. If $p\not\equiv1\pmod 3$, then this follows from the fact that $k\mapsto k^3$ is a permutation of the
elements of the group $\mathbb{Z}_p^*$. OTOH, if $p\equiv1\pmod3$, then
$k\mapsto k^3$ is a 3-1 mapping attaining all cubic residues modulo $p$ as a value thrice. Because $-1$ is a cubic residue, the $(p-1)/3$ cubic residues come in pairs:$\{a,p-a\}$. The claim follows in this case as well.
Thus
$$
A-B=\frac{p-1}2.
$$
It is known that
$$
A=\frac14p(p-1)^2.
$$
The claim follows from the calculation
$$
B=A-\frac{p-1}2=\frac14[p(p-1)^2-2(p-1)]=\frac14(p-1)(p^2-p-2).
$$
A: For each $1\leq k\leq p-1$ we can write $$k^3=q_kp+r_k$$and $$q_k=\left\lfloor\frac{k^3}{p}\right\rfloor\;\;,\;\;0\leqslant r_k<p-1$$
Now, we obtain that $$\sum_{k=1}^{p-1}k^3=p\sum_{k=1}^{p-1}\left\lfloor\frac{k^3}{p}\right\rfloor+\sum_{k=1}^{p-1}r_k$$
It is well known that $$\sum_{k=1}^{p-1}k^3=\left[\frac{p(p-1)}{2}\right]^2$$
so we get that $$\frac{{p{{\left( {p - 1} \right)}^2}}}{4} - \frac{1}{p}\sum\limits_{k = 1}^{p - 1} {{r_k}}  = \sum\limits_{k = 1}^{p - 1} {\left\lfloor {\frac{{{k^3}}}{p}} \right\rfloor } $$ 
Thus, it remains to determine $$\sum_{k=1}^{p-1}r_k$$ which in light of your formula must be $$\frac{{p\left( {p - 1} \right)}}{2} = \sum\limits_{k = 1}^{p - 1} {{r_k}} $$
Now, we make the simple observation that, mod $p$, we have $$x^3+(p-x)^3=0\mod p$$
Since residues are $<p$ but here they sum to a multiple of $p$, this multiple must be $p$, whence we have $(p-1)/2$ pairs that sum to $p$, whence their sum must be $$\frac{p(p-1)}{2}$$ and we're done.
