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!

Sums of natural numbers to p and subsequent divisibility

  1. Oct 17, 2007 #1
    So I'm taking an introductory number theory course as an undergraduate, and this particular "genre" of questions really just has me stumped.

    Pick a prime [tex]p[/tex] such that [tex]p[/tex] is odd. Now, take various sums up of natural numbers from 1 to [tex]p[/tex], and show that the results are divisible by [tex]p[/tex].

    For example, consider,

    [tex]n = 1\cdot 2 + 2\cdot 3 + \cdots + (p-1)\cdot p[/tex]

    And show that it is divisible by [tex]p[/tex].

    Now in my notes, I have something about polynomial congruences, and how the coefficients must all be equal. And I have the congruence,

    [tex]x^p - x \equiv (x-1)(x-2)\cdots (x-p) \bmod p[/tex]

    Which apparently helped find the result, but I'm not sure why. It made sense when I wrote it down, but now I'm drawing a blank.

    Can anyone maybe help me fill in the gaps?
     
  2. jcsd
  3. Oct 17, 2007 #2
    In retrospect, this post may not belong in this particular sub forum, as it does relate to a course I'm taking.
     
  4. Oct 18, 2007 #3

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Am I reading this correctly? For p= 3, which is certainly an odd prime, that is
    [tex]n= 1\cdot 2+ 2\cdot 3= 2+ 6= 8[/itex]
    which is clearly NOT divisible by p= 3.

     
  5. Oct 18, 2007 #4
    My mistake, it has to be an odd prime greater than 3.
     
  6. Oct 18, 2007 #5

    morphism

    User Avatar
    Science Advisor
    Homework Helper

    Try to expand the right side to see what the coefficient of x^(p-2) looks like.
     
  7. Oct 18, 2007 #6
    Wow...what I had here was really bad...working on it, still..
     
    Last edited: Oct 18, 2007
  8. Oct 18, 2007 #7
    Wait...no...that's not right.
     
  9. Oct 18, 2007 #8
    Clearly [tex] p! \equiv 0 \bmod p [/tex] since [tex]p \equiv 0 \bmod p [/tex]. Now it's also not to hard to see that

    [tex] (p-1)! \equiv -1 \bmod p [/tex]
     
  10. Oct 18, 2007 #9
    Yeah, that's a result that my text has, actually. I've felt like it would play a role for a while now.


    I think I'm finally starting to understand this concept though. Let me know, if you would, if this line of thought seems correct:

    Say instead of the [tex]n[/tex] I originally introduced, I instead consider a simpler case first. Let

    [tex]m=1+2+\cdots +p[/tex]

    So then if I take the known congruence

    [tex]x^p-x\equiv(x-1)(x-2)\cdots (x-p) \bmod p[/tex]

    And expand the right hand side, the coefficients of [tex]x^{p-1}[/tex] should (in this case) be a complete residue system mod [tex]p[/tex]. So then adding them together would give me, essentially, [tex]1+2+\cdots +p[/tex] or [tex]m[/tex]. And I know that this value needs to be congruent to whatever the coefficient of [tex]x^{p-1}[/tex] is on the left hand side of the original congruence, which in this case is zero. Hence, [tex]0\equiv m \bmod p[/tex] or [tex]p\mid m[/tex].


    And then from here, I should be able to extend this to the [tex]x^{p-2}[/tex] coefficients, which should give me [tex]p\mid n[/tex], where

    [tex]n=1\cdot 2 + 1\cdot 3 + \cdots + (p-1)\cdot p[/tex]

    Does this seem right?
     
  11. Oct 19, 2007 #10

    morphism

    User Avatar
    Science Advisor
    Homework Helper

    Yes. The coefficient of x^(p-2) is n. And if p is a prime greater than 3, then the coefficient of x^(p-2) on the left side of your original equation is 0. So n=0 (mod p).
     
  12. Oct 19, 2007 #11

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Are you sure of that? Isn't the coefficient of x^(p-2) the sum of the products of ALL unequal pairs of integers between 1 and p? Not just 1*2+2*3+3*4+...+(p-1)*p?
     
  13. Oct 19, 2007 #12
    That's what I had originally meant, yeah. It's sort of hard to write it out, I've found. It's something like

    [tex]1\cdot 2 + 1\cdot 3 \cdots 1 \cdot p + 2\cdot 3 +2\cdot 4 \cdots (p-1)\cdot p[/tex],

    I believe.
     
  14. Oct 19, 2007 #13

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Maybe we are just looking at the wrong clues. There is an elementary way to do this. Your sum terms are i*(i+1)=i^2+i. There are formulas to let you write out this sum as an explicit polynomial. Now figure out under what conditions that polynomial is divisible by p. It works for more than just primes bigger than 3. I claim 1*2+2*3+...+(n-1)*n is divisible by n for any n that is not divisible by 3.
     
  15. Oct 19, 2007 #14
    Interesting. I know the question my professor posed was only for primes, but I may toy with this just to see, and maybe help my understanding of the concept as a whole.
     
  16. Oct 19, 2007 #15

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Don't toy with it. Just do it. 'elementary' means 'not even hard'.
     
  17. Oct 19, 2007 #16
    Well isn't that very modest of you to say. I'm glad your username really fits your personality, or so it seems.
     
  18. Oct 19, 2007 #17

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Oh, come on. You can sum i^2 and you can sum i. If you wish, I can cease contributing. A 'thanks for helping' would be more in order. My user name is my own. Thanks.
     
  19. Oct 19, 2007 #18
    What is 2*n!/3!(n-3)!
     
  20. Oct 20, 2007 #19

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I tried this. It works. In fact (if I didn't screw up somewhere)

    [tex](\sum_1^p n)^2 - \sum_1^p n^2 \equiv 0~(mod~p) [/tex]

    for all odd p not divisible by 3.
     
  21. Oct 20, 2007 #20

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Ah, ha. It looked to me like the sum the OP wanted was
    [tex]\sum_1^{p-1} n(n+1)[/tex]
    I don't think I guessed the intended series correctly.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?