1
$\begingroup$

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.

3 Answers 3

2

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)] 
  • 0
    @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...2012-12-02
10

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.

  • 0
    @misi10: A hint would be *approach it the same way that I approached the first problem*, but I’ve actually done more than that.2012-12-02
3

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$

  • 0
    @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.2012-12-02