1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Apr 3, 2012 #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. Apr 3, 2012 #2

    Mark44

    User Avatar
    Insights Author

    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. Apr 3, 2012 #3

    Mark44

    User Avatar
    Insights Author

    Staff: Mentor

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

    Mark44

    User Avatar
    Insights Author

    Staff: Mentor

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

    1 ≠ 0 (mod 2)
     
  7. Apr 3, 2012 #6
    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. Apr 3, 2012 #7
    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. Apr 3, 2012 #8

    Mark44

    User Avatar
    Insights Author

    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 thread via Reddit, Google+, Twitter, or Facebook

Have something to add?