1 + 2 + 3 + + (p-1)(mod p)

  1. 1. The problem statement, all variables and given/known data
    What is the value of 1 + 2 + 3 +...+ (p-1)(mod p)?


    2. Relevant equations

    p = 0 (mod p)
    p-1 = -1 (mod p)
    1 + 2 + 3 + ...+n = n(n+1)/2

    3. The attempt at a solution

    I know 1 + 2 + 3 +...+ (p-1) = (p-1)(p)/2

    I worked the problem, but i don't know if i am correct:

    work: i am looking for a b s.t.

    b = (p-1)(p)/2 (mod p) or 2b = (p-1)(p) ( mod p)
    we know (p-1) = -1 (mod p)
    so : (p-1)p = -p (mod p)
    this implies : 2b = -p(mod p) ,also we know p = 0 (mod p) so b =0 (mod p)

    So the answer is 1 + 2 + 3 +...+ (p-1) = 0 (mod p)
     
  2. jcsd
  3. Mark44

    Staff: Mentor

    I get different answers depending on whether p is even or odd.

    For example, if p = 6, 1 + 2 + 3 + 4 + 5 ##\equiv## 3 (mod 6).

    If p = 5, 1 + 2 + 3 + 4 ##\equiv## 0 (mod 5).
     
  4. Mark44

    Staff: Mentor

    BTW, what you're calculating is (1 + 2 + ... + (p -1))(mod p).
     
  5. Mark, I am sorry I was not clear, when I say p I mean a prime number.
     
  6. Mark44

    Staff: Mentor

    How about if p = 2, the only even prime?

    1 ≠ 0 (mod 2)
     
  7. Well, you have the right idea by writting
    [tex]1+2+\cdots+(p-1) = \frac{(p-1)p}{2}[/tex]

    But then you sort of take the long route to the eventual answer.

    When you have this:
    [tex]1 + \cdots + (p-1) = \frac{(p-1)p}{2}[/tex]

    just note that [itex]p-1[/itex] is even so that [itex](p-1)/2[/itex] is an integer. Thus, the sum is divisible by [itex]p[/itex] and so the answer is [itex]0[/itex].

    But, yes, your answer is correct.

    EDIT:
    As Mark mentioned, you'll have to do a special case for 2. In fact, this happens a lot in Number Theory.
     
  8. I see.
    So if p=2 then I know the sum is : 1 + 1 = 2, which is congruent to 0 mod 2 as well.

    Thank you both for you help!
     
  9. Mark44

    Staff: Mentor

    No. If p = 2, the sum has only one term (you quit at 2 - 1 = 1).
     
Know someone interested in this topic? Share this thead via email, Google+, Twitter, or Facebook

Have something to add?