How to solve $ \sum_{i=1}^{n-1} i^2 \equiv \;? \pmod n$ I solved expressions below . it is ok?
My attempt:
$$1)\;\;\;\;\; ?\cong\pmod n\sum_{i=1}^{n-1} i^2 \stackrel{?}=   {(n-1)^3\over3}+{(n-1)^2\over2}+{(n-1)\over6}={n^3\over3}-{n^2\over6}+{n\over6}=n\left({n^2\over3}-{n\over2}+{1\over6}\right)
 $$
(continue?)how to solve for all n?
$$2)\;\;\;\;\;?\cong\pmod n \sum_{i=1}^{n-1} i^3 = \left( {(n-1)n\over2} \right)^2$$
(continue?)how to solve for all n?
Thank you.
 A: You know that 
First, since $n^2 =0 \pmod n$ and $n^3 =0 \pmod n$, you can calculate the sum up to $n$.
(i)
$$\sum_{i=1}^{n-1} i^2 =\sum_{i=1}^{n} i^2 =\frac{n(n+1)(2n+1)}{6} \pmod n$$
Thus, you have to decide which of the terms is divisible by 2,3. CRT tells you this is a problem modulo 6.
Now a case by case analysis solves it:
Case 1: $n=6k$. Then
$$ \frac{n(n+1)(2n+1)}{6} \equiv k (n+1)(2n+1) \equiv k \equiv \frac{n}{6}  \pmod n$$
Case 2: $n=6k+1$. Then $n+1=2(3k+1)$ and $n+2=3(2k+1)$
$$ \frac{n(n+1)(2n+1)}{6} \equiv n(3k+1)(2k+1) \equiv 0 \pmod n$$
the other cases are similar.
(ii) This is easier
$$\sum_{i=1}^{n-1} i^3 =\sum_{i=1}^{n} i^3 =\frac{n^2(n+1)^2}{4} \pmod n$$
We only have two cases now, odd or even.
Case 1: $n=2k$. Then
$$ \frac{n^2(n+1)^2}{4} \equiv k^2 (n+1)^2 \equiv k^2 \equiv \frac{n^2}{4}  \pmod n$$
Case 2: $n=2k+1$. Then $n+1=2(k+1)$ 
$$ \frac{n^2(n+1)^2}{2} \equiv n^2(k+1)^2 \equiv 0 \pmod n$$
A: That problem, generalized to any exponent m instead of 2 is considered in the context of the Agoh-Giuga-conjecture, the perhaps most interesting articles about this are of Bernd Kellner, of the Borweins, and of WD Banks (all of them online available).       You might also consider to look at this earlier question at MSE of mine)
For the problem: 
$$ S_m(n) = \sum_{k=1}^{n-1} k^m \pmod n  $$
one can even heuristically arrive at the following formula:
$$ S_m(n) = n \cdot \sum_{\begin{array} {c} p | n \\ p-1 |m \end{array}} (1- \frac1p)  \pmod n $$
or, in this case
$$ S_2(n) = n \cdot \sum_{\begin{array} {c} p | n \\ p-1 |2 \end{array}} (1- \frac1p)  \pmod n $$
which, because $p=2$ and $p=3$ are the only prime where $p-1$ divides $2$
$$ S_2(n) = n\cdot ([n:3] \frac 23 + [n:2] \frac 12)   \pmod n $$
where I write $[a:b]$ for the Iverson-bracket, which evaluates to 1 if b divides a, and to zero, if not.

Here is some Pari/GP-code to work with this:

su(n)=n*(1/6 + 1/2*n + 1/3*n^2)  \\ by the known sum-formula 
                                 \\       from Bernoulli-polynomials
sumod(n) = su(n-1) % n           \\ taken modulo n

    \\ now the same by the primefactor-based formula 
sumod1(n) = ( (n % 3==0)*2*n/3 + (n % 2==0)*n/2 ) % n


\\ check this with some n
[n =8*74*3^2, sumod (n) ,  sumod1 (n)]

A: It never hurts to gather some numerical data. For your first problem:
$$\begin{array}{cc|cc|cc}
n&\left(\sum_{k=1}^{n-1}k^2\right)\bmod n&n&\left(\sum_{k=1}^{n-1}k^2\right)\bmod n&n&\left(\sum_{k=1}^{n-1}k^2\right)\bmod n\\ \hline
2&1&8&4&14&7\\
3&2&9&6&15&10\\
4&2&10&5&16&8\\
5&0&11&0&17&0\\
6&1&12&2&18&3\\
7&0&13&0&19&0
\end{array}$$
Examination of that table should suggest that
$$\left(\sum_{k=1}^{n-1}k^2\right)\bmod n=\begin{cases}
\frac{n}2,&\text{if }n\equiv 2\!\!\!\pmod 6\\\\
\frac{2n}3,&\text{if }n\equiv 3\!\!\!\pmod 6\\\\
\frac{n}2,&\text{if }n\equiv 4\!\!\!\pmod 6\\\\
0,&\text{if }n\equiv 5\!\!\!\pmod 6\\\\
\frac{n}6,&\text{if }n\equiv 0\!\!\!\pmod 6\\\\
0,&\text{if }n\equiv 1\!\!\!\pmod 6\;;
\end{cases}\tag{1}$$
since you know that $$\sum_{k=1}^{n-1}k^2=n\left(\frac{n^2}3-\frac{n}2+\frac16\right)=\frac16n(n-1)(2n-1)\;,$$ it shouldn’t be too hard to prove $(1)$.
Added: For the second problem, did you try calculating 
$$\left(\sum_{k=1}^{n-1}k^3\right)\bmod n=\frac{n^2(n-1)^2}4\bmod n$$
for $n=2,3,4,\dots$ as I did for the first problem? Doing so should let you guess right away that the value is $0$ for odd $n$, and discovering the mathematical reason for this isn’t hard. If $n$ is odd, then $\frac{(n-1)^2}4$ is an integer, and clearly $n^2\frac{(n-1)^2}4\bmod n=0$.
If $n$ is even, then 
$$\frac{n^2(n-1)^2}4\equiv\left(\frac{n}2\right)^2(n-1)^2\equiv\left(\frac{n}2\right)(-1)^2\equiv\left(\frac{n}2\right)^2\pmod n\;.$$
Now make a table for $n=2,4,6,\dots$:
$$\begin{array}{rccc}
n:&2&4&6&8&10&12&14&16\\ \hline
\left(\frac{n}2\right)^2\bmod n:&1&0&3&0&5&0&7&0
\end{array}$$
The pattern is pretty obvious: it definitely appears that
$$\left(\frac{n}2\right)^2\bmod n=\begin{cases}
0,&\text{if }n\equiv 0\!\!\!\pmod 4\\\\
n/2,&\text{if }n\equiv 2\!\!\!\pmod 4\;,
\end{cases}$$
and you shouldn’t have too much trouble proving that this is actually the case.
