Summation up to p-1 modulo p, p prime

What is the value of $\displaystyle 1+2+...+(p-1) \equiv (mod p)$? $\displaystyle 1^{2} + 2^{2} + ... + (p-1)^{2} \equiv (mod p)$? For any positive integer k, find the value of $\displaystyle 1^{k} + 2^{k} + ... + (p-1)^{k} \equiv (mod p)$ and prove your assertion is correct?

So I simply tested out values, and for a lot of primes and powers, it's simply 0, but sometimes, when $\displaystyle p=3$, for example, it's sometimes either 0 or 2, like when $\displaystyle k=10$ it's 2, but when $\displaystyle k=11$, it's 0. I can't come up with a clear formula for any of these values.

Re: Summation up to p-1 modulo p, p prime

Quote:

Originally Posted by

**Pinkk** What is the value of $\displaystyle 1+2+...+(p-1) \equiv (mod p)$? $\displaystyle 1^{2} + 2^{2} + ... + (p-1)^{2} \equiv (mod p)$? For any positive integer k, find the value of $\displaystyle 1^{k} + 2^{k} + ... + (p-1)^{k} \equiv (mod p)$ and prove your assertion is correct?

So I simply tested out values, and for a lot of primes and powers, it's simply 0, but sometimes, when $\displaystyle p=3$, for example, it's sometimes either 0 or 2, like when $\displaystyle k=10$ it's 2, but when $\displaystyle k=11$, it's 0. I can't come up with a clear formula for any of these values.

Here is a hint:

change the order that you are adding and use the associative property to get

$\displaystyle 1+(p-1)+2+(p-2)+...=p+p+p+... $

Note that the number of terms depends on if p is even or odd.

Re: Summation up to p-1 modulo p, p prime

Sorry one more hint is

$\displaystyle (p-n)^k \mod p=n^k \mod p$ why is this true?

Re: Summation up to p-1 modulo p, p prime

Isn't it actually either $\displaystyle n^{k}$ or $\displaystyle -n^{k}$ depending on whether k is odd or even? I mean, I understand that you'd use the binomial theorem and that all terms except the $\displaystyle n^{k}$ term has factors of p in it, and are therefore 0 modulo p.

Re: Summation up to p-1 modulo p, p prime

Quote:

Originally Posted by

**Pinkk** Isn't it actually either $\displaystyle n^{k}$ or $\displaystyle -n^{k}$ depending on whether k is odd or even? I mean, I understand that you'd use the binomial theorem and that all terms except the $\displaystyle n^{k}$ term has factors of p in it, and are therefore 0 modulo p.

You are correct. I left out a factor of $\displaystyle (-1)^k$

Re: Summation up to p-1 modulo p, p prime

I'm still not sure how this helps, or rather, how it explains why for even powers, using p=3 gives me 2 while using odd powers gives me 0, whereas with p=5 or p=7, say, it doesn't matter.

Re: Summation up to p-1 modulo p, p prime

Quote:

Originally Posted by

**Pinkk** I'm still not sure how this helps, or rather, how it explains why for even powers, using p=3 gives me 2 while using odd powers gives me 0, whereas with p=5 or p=7, say, it doesn't matter.

We can do this in two steps. In any commutative unital ring of odd characteristic one has that $\displaystyle \displaystyle \sum_{j=1}^{x}j=\frac{x(x+1)}{2}$. So, if the ring is $\displaystyle \mathbb{Z}/p\mathbb{Z}$ and $\displaystyle x=p-1$ then we get that $\displaystyle \displaystyle \sum_{j=1}^{p-1}j=\frac{(p-1)p}{2}\equiv0\text{ mod }p$. If $\displaystyle p=2$ then you can quickly check (since we can't apply the same method) that $\displaystyle 0+1\qeuiv 1\text{ mod }2$. You can proceed for the summing of squres similarly.

Re: Summation up to p-1 modulo p, p prime

Well, this is for number theory class so we haven't covered or used anything regarding rings so we really couldn't use anything like that on an exam. And yeah, it is easy to show when just k=1 that it's 0 for all primes greater than 2, but when it gets to squares or k in general, I'm still lost and I can't figure out a general expression of the value.

I mean, if k is even then the summation of the k-th powers of 1 through p-1 modulo p is $\displaystyle 2(1^{k} + 2^{k} + ... + (\frac{p-1}{2})^{k})$ Other than knowing that, I'm lost.

Re: Summation up to p-1 modulo p, p prime

Let $\displaystyle S_p^r = \sum_{k=0}^{p-1} k^r$. Then $\displaystyle S_p^r \equiv 0 \pmod {p}$ for every prime $\displaystyle p$ and $\displaystyle 0\le r \le p-2$.

**Proof:**

Consider:

$\displaystyle (k+1)^{n+1}-k^{n+1} = \sum_{r=0}^{n} \binom{n+1}{r} k^r$

Summing all these equalities for $\displaystyle 0 \le k \le p-1$ we get:

$\displaystyle \sum_{r=0}^{n} \binom{n+1}{r} S_p^r = p^{n+1} \equiv 0 \pmod{p}$

So:

$\displaystyle (n+1)S_p^n \equiv -\sum_{r=0}^{n-1} \binom{n+1}{r} S_p^r \pmod{p}$

Therefore we get the result by induction.

Re: Summation up to p-1 modulo p, p prime

In the last line, are you using the fact that $\displaystyle n+1< p$, so therefore it's $\displaystyle S_{p}^{n}$ that is 0 modulo p? If that's the case, then I understand it now. But what about for r in general, is there no clear formula?

Re: Summation up to p-1 modulo p, p prime

My point was that if $\displaystyle p\ne 2$ then the power sum formula you know and love $\displaystyle 1+\cdots+n$=\frac{1}{2}n(n+1)[/tex] is true, if $\displaystyle p\ne 2,3$ then $\displaystyle 1+\cdots+n^2=\frac{1}{6}n(n+1)(2n+1)$ holds true, etc. Namely, if you have a power sum formula and you're dealing with a prime which doesn't divide the denominator of the formula then it still works.

Re: Summation up to p-1 modulo p, p prime

Oh, okay. I did figure that for squares if p does not divide 6 (i.e. when p=2 or p=3) then it is 0 modulo p, but I'm guessing there is no clean formula for all values k and all primes p?

Re: Summation up to p-1 modulo p, p prime

Quote:

Originally Posted by

**Pinkk** Oh, okay. I did figure that for squares if p does not divide 6 (i.e. when p=2 or p=3) then it is 0 modulo p, but I'm guessing there is no clean formula for all values k and all primes p?

Formula for what? If you mean modulo the prime, then as **Unbeatable** pointed out it's zero if the prime is odd and one otherwise (this is clear from what I said as well since $\displaystyle n$ always divides the sum). If you mean for the actual formulas, there is no nice formula. Did you look at that link that I sent you?

Re: Summation up to p-1 modulo p, p prime

it seems to me that by post #2 (and #5), we know that $\displaystyle (p-n)^k = (-1)^kn^k\ (mod\ p)$.

if p = 2, we always get 1, no matter what k is. otherwise p is an odd prime.

if k is odd, we can pair n with p-n, we have (p-1)/2 such pairs, which will always sum to 0 (mod p).

if k is even, the situation is more complicated. for example:

$\displaystyle \sum_{n=1}^{p-1} n^6 = \frac{(p-1)(p)(2p-1)(3(p-1)^4 + 6(p-1)^3 -3(p-1) + 1)}{42}$

but we cannot apply this formula for p = 2,3 or 7. indeed,

$\displaystyle 1^6 + 2^6 + 3^6 + 4^6 + 5^6 + 6^6 = 6\ (mod\ 7)$

"most" of the sums of 6th powers will sum to 0 (mod p), but we will have exceptions (prime divisors of 42).

i suspect that, in the even k case, the exceptions always sum to p-1 (mod p), but i have not seen (in this thread, at any rate) a proof of that, or a way to enumerate which p will prove exceptional.

Quote:

Originally Posted by

**Drexel28** Formula for what? If you mean modulo the prime, then as **Unbeatable** pointed out it's zero if the prime is odd and one otherwise (this is clear from what I said as well since $\displaystyle n$ always divides the sum). If you mean for the actual formulas, there is no nice formula. Did you look at that link that I sent you?

this is untrue.

Re: Summation up to p-1 modulo p, p prime

Quote:

Originally Posted by

**Deveno**

this is untrue.

What is untrue about it? Perhaps I was unclear in my wording. It's zero when the prime is odd for the case $\displaystyle \displaystyle \sum k$. Beyond that it's not clear how exactly it reacts. It's clear though, as I was trying to get across, that when summing $\displaystyle \displaystyle \sum k^m$ gives you zero is highly connected to the constant in the denonminator of the formula for the sum since, if a prime doesn't divide this denominator then the sum is zero.