# Summation up to p-1 modulo p, p prime

Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last
• Oct 20th 2011, 04:37 PM
Pinkk
Summation up to p-1 modulo p, p prime
What is the value of $1+2+...+(p-1) \equiv (mod p)$? $1^{2} + 2^{2} + ... + (p-1)^{2} \equiv (mod p)$? For any positive integer k, find the value of $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 $p=3$, for example, it's sometimes either 0 or 2, like when $k=10$ it's 2, but when $k=11$, it's 0. I can't come up with a clear formula for any of these values.
• Oct 20th 2011, 04:45 PM
TheEmptySet
Re: Summation up to p-1 modulo p, p prime
Quote:

Originally Posted by Pinkk
What is the value of $1+2+...+(p-1) \equiv (mod p)$? $1^{2} + 2^{2} + ... + (p-1)^{2} \equiv (mod p)$? For any positive integer k, find the value of $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 $p=3$, for example, it's sometimes either 0 or 2, like when $k=10$ it's 2, but when $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

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

Note that the number of terms depends on if p is even or odd.
• Oct 20th 2011, 04:50 PM
TheEmptySet
Re: Summation up to p-1 modulo p, p prime
Sorry one more hint is

$(p-n)^k \mod p=n^k \mod p$ why is this true?
• Oct 20th 2011, 05:06 PM
Pinkk
Re: Summation up to p-1 modulo p, p prime
Isn't it actually either $n^{k}$ or $-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 $n^{k}$ term has factors of p in it, and are therefore 0 modulo p.
• Oct 20th 2011, 05:14 PM
TheEmptySet
Re: Summation up to p-1 modulo p, p prime
Quote:

Originally Posted by Pinkk
Isn't it actually either $n^{k}$ or $-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 $n^{k}$ term has factors of p in it, and are therefore 0 modulo p.

You are correct. I left out a factor of $(-1)^k$
• Oct 20th 2011, 05:20 PM
Pinkk
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.
• Oct 20th 2011, 05:41 PM
Drexel28
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 \sum_{j=1}^{x}j=\frac{x(x+1)}{2}$. So, if the ring is $\mathbb{Z}/p\mathbb{Z}$ and $x=p-1$ then we get that $\displaystyle \sum_{j=1}^{p-1}j=\frac{(p-1)p}{2}\equiv0\text{ mod }p$. If $p=2$ then you can quickly check (since we can't apply the same method) that $0+1\qeuiv 1\text{ mod }2$. You can proceed for the summing of squres similarly.
• Oct 20th 2011, 05:51 PM
Pinkk
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 $2(1^{k} + 2^{k} + ... + (\frac{p-1}{2})^{k})$ Other than knowing that, I'm lost.
• Oct 20th 2011, 06:30 PM
Unbeatable0
Re: Summation up to p-1 modulo p, p prime
Let $S_p^r = \sum_{k=0}^{p-1} k^r$. Then $S_p^r \equiv 0 \pmod {p}$ for every prime $p$ and $0\le r \le p-2$.

Proof:

Consider:

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

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

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

So:

$(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.
• Oct 20th 2011, 07:12 PM
Pinkk
Re: Summation up to p-1 modulo p, p prime
In the last line, are you using the fact that $n+1< p$, so therefore it's $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?
• Oct 20th 2011, 07:35 PM
Drexel28
Re: Summation up to p-1 modulo p, p prime
My point was that if $p\ne 2$ then the power sum formula you know and love $1+\cdots+n$=\frac{1}{2}n(n+1)[/tex] is true, if $p\ne 2,3$ then $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.
• Oct 20th 2011, 08:09 PM
Pinkk
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?
• Oct 20th 2011, 08:17 PM
Drexel28
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 $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?
• Oct 20th 2011, 08:24 PM
Deveno
Re: Summation up to p-1 modulo p, p prime
it seems to me that by post #2 (and #5), we know that $(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:

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

$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 $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.
• Oct 21st 2011, 12:41 AM
Drexel28
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 \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 \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.
Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last