• Support PF! Buy your school textbooks, materials and every day products Here!

Sums of natural numbers to p and subsequent divisibility

  • #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?
 

Answers and Replies

  • #2
In retrospect, this post may not belong in this particular sub forum, as it does relate to a course I'm taking.
 
  • #3
HallsofIvy
Science Advisor
Homework Helper
41,770
911
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].
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.

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?
 
  • #4
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.
My mistake, it has to be an odd prime greater than 3.
 
  • #5
morphism
Science Advisor
Homework Helper
2,015
4
[tex]x^p - x \equiv (x-1)(x-2)\cdots (x-p) \bmod p[/tex]
Try to expand the right side to see what the coefficient of x^(p-2) looks like.
 
  • #6
Wow...what I had here was really bad...working on it, still..
 
Last edited:
  • #7
Wait...no...that's not right.
 
  • #8
743
1
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]
 
  • #9
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]
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?
 
  • #10
morphism
Science Advisor
Homework Helper
2,015
4
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).
 
  • #11
Dick
Science Advisor
Homework Helper
26,258
618
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).
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?
 
  • #12
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?
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.
 
  • #13
Dick
Science Advisor
Homework Helper
26,258
618
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.
 
  • #14
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.
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.
 
  • #15
Dick
Science Advisor
Homework Helper
26,258
618
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.
Don't toy with it. Just do it. 'elementary' means 'not even hard'.
 
  • #16
Don't toy with it. Just do it. 'elementary' means 'not even hard'.
Well isn't that very modest of you to say. I'm glad your username really fits your personality, or so it seems.
 
  • #17
Dick
Science Advisor
Homework Helper
26,258
618
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.
 
  • #18
841
0
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]
wrote it down, but now I'm drawing a blank.

Can anyone maybe help me fill in the gaps?
What is 2*n!/3!(n-3)!
 
  • #19
Gokul43201
Staff Emeritus
Science Advisor
Gold Member
7,051
16
Don't toy with it. Just do it. 'elementary' means 'not even hard'.
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.
 
  • #20
Dick
Science Advisor
Homework Helper
26,258
618
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.
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.
 
  • #21
Gokul43201
Staff Emeritus
Science Advisor
Gold Member
7,051
16
You had it right in post #11. That's the sum I checked.
 
  • #22
Gib Z
Homework Helper
3,346
4
In reference to post 16, he hasnt even said sorry, why are we still helping him..
 
  • #23
Dick
Science Advisor
Homework Helper
26,258
618
Because I thought that 1*2+2*3+...+(p-1)p was the series I mentioned in post 20. The correct interpretation is the one Gokul and morphism gave it. This isn't 'help', I'm just trying to make sure my confusion doesn't spread.
 

Related Threads for: Sums of natural numbers to p and subsequent divisibility

Replies
8
Views
426
Replies
1
Views
2K
Replies
1
Views
4K
  • Last Post
Replies
0
Views
1K
Replies
3
Views
998
Replies
8
Views
1K
Replies
4
Views
2K
Top