Page 1 of 2 12 LastLast
Results 1 to 15 of 18

Math Help - Summation up to p-1 modulo p, p prime

  1. #1
    Senior Member Pinkk's Avatar
    Joined
    Mar 2009
    From
    Uptown Manhattan, NY, USA
    Posts
    419

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Behold, the power of SARDINES!
    TheEmptySet's Avatar
    Joined
    Feb 2008
    From
    Yuma, AZ, USA
    Posts
    3,764
    Thanks
    78

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

    Quote Originally Posted by Pinkk View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Behold, the power of SARDINES!
    TheEmptySet's Avatar
    Joined
    Feb 2008
    From
    Yuma, AZ, USA
    Posts
    3,764
    Thanks
    78

    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member Pinkk's Avatar
    Joined
    Mar 2009
    From
    Uptown Manhattan, NY, USA
    Posts
    419

    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Behold, the power of SARDINES!
    TheEmptySet's Avatar
    Joined
    Feb 2008
    From
    Yuma, AZ, USA
    Posts
    3,764
    Thanks
    78

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

    Quote Originally Posted by Pinkk View Post
    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
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member Pinkk's Avatar
    Joined
    Mar 2009
    From
    Uptown Manhattan, NY, USA
    Posts
    419

    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21

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

    Quote Originally Posted by Pinkk View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member Pinkk's Avatar
    Joined
    Mar 2009
    From
    Uptown Manhattan, NY, USA
    Posts
    419

    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.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Nov 2009
    Posts
    106

    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.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Senior Member Pinkk's Avatar
    Joined
    Mar 2009
    From
    Uptown Manhattan, NY, USA
    Posts
    419

    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?
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21

    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.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Senior Member Pinkk's Avatar
    Joined
    Mar 2009
    From
    Uptown Manhattan, NY, USA
    Posts
    419

    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?
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21

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

    Quote Originally Posted by Pinkk View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,150
    Thanks
    591

    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 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21

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

    Quote Originally Posted by Deveno View Post


    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.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. If a has order n - 1 modulo n, then n is prime.
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 10th 2011, 12:29 PM
  2. prime and modulo proofs
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: February 22nd 2011, 02:43 AM
  3. Help with prime number and modulo
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: July 12th 2010, 11:10 PM
  4. square modulo the prime...
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 12th 2010, 07:10 AM
  5. Order modulo a prime
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: March 22nd 2010, 02:25 PM

Search Tags


/mathhelpforum @mathhelpforum