# 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.

-

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$$

-
I don't know how to identify problem is modulo 6 ,and in 2) n=2k , n= 2k+1 – misi10 Dec 2 '12 at 19:15
For the first problem you know what the top is modulo $n$, but you need to divide by $6$. You know that each of 2,3 divide one of the terms at the top, but you don't know which one... Thus the question becomes: which of $n,n+1, 2n+1$ is divisible by $2$ respectively $3$.... These are two questions modulo 2 and modulo 3... So you need to study $n$ modulo 2 and $n$ modulo 3. – N. S. Dec 2 '12 at 19:24
@misi10 For the second question the RHS is $(\frac{n(n+1)}{2})^2$. Again, you know $n, n+1$ modulo n, but you also need to divide by $2$, and you don't know which one is divisible by $2$... That's why the two cases. – N. S. Dec 2 '12 at 19:26

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.

-
for 2) can you give me HINT? – misi10 Dec 2 '12 at 17:18
@misi10: A hint would be approach it the same way that I approached the first problem, but I’ve actually done more than that. – Brian M. Scott Dec 2 '12 at 21:32

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)]

-
How to arrive $S_m(n) = \sum_{k=1}^{n-1} k^m \pmod n$ --> $S_m(n) = \sum_{\begin{array} {c} p | n \\ p-1 |m \end{array}} (1- \frac1p) \pmod n$ and write out more? – misi10 Dec 2 '12 at 14:23
@misi10: I found it myself by examination of the pattern of the results which I got using the original formulation of the problem with various m. But Kellner, and I think Banks (but with the latter I am not sure), gives a proof for that identity as far as I recall... – Gottfried Helms Dec 2 '12 at 17:57