# Sums of natural numbers to p and subsequent divisibility

1. Oct 17, 2007

### thirdchildikari

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 $$p$$ such that $$p$$ is odd. Now, take various sums up of natural numbers from 1 to $$p$$, and show that the results are divisible by $$p$$.

For example, consider,

$$n = 1\cdot 2 + 2\cdot 3 + \cdots + (p-1)\cdot p$$

And show that it is divisible by $$p$$.

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

$$x^p - x \equiv (x-1)(x-2)\cdots (x-p) \bmod p$$

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. Oct 17, 2007

### thirdchildikari

In retrospect, this post may not belong in this particular sub forum, as it does relate to a course I'm taking.

3. Oct 18, 2007

### HallsofIvy

Staff Emeritus
Am I reading this correctly? For p= 3, which is certainly an odd prime, that is
$$n= 1\cdot 2+ 2\cdot 3= 2+ 6= 8[/itex] which is clearly NOT divisible by p= 3. 4. Oct 18, 2007 ### thirdchildikari My mistake, it has to be an odd prime greater than 3. 5. Oct 18, 2007 ### morphism Try to expand the right side to see what the coefficient of x^(p-2) looks like. 6. Oct 18, 2007 ### thirdchildikari Wow...what I had here was really bad...working on it, still.. Last edited: Oct 18, 2007 7. Oct 18, 2007 ### thirdchildikari Wait...no...that's not right. 8. Oct 18, 2007 ### Kreizhn Clearly [tex] p! \equiv 0 \bmod p$$ since $$p \equiv 0 \bmod p$$. Now it's also not to hard to see that

$$(p-1)! \equiv -1 \bmod p$$

9. Oct 18, 2007

### thirdchildikari

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 $$n$$ I originally introduced, I instead consider a simpler case first. Let

$$m=1+2+\cdots +p$$

So then if I take the known congruence

$$x^p-x\equiv(x-1)(x-2)\cdots (x-p) \bmod p$$

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

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

$$n=1\cdot 2 + 1\cdot 3 + \cdots + (p-1)\cdot p$$

Does this seem right?

10. Oct 19, 2007

### morphism

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. Oct 19, 2007

### Dick

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. Oct 19, 2007

### thirdchildikari

That's what I had originally meant, yeah. It's sort of hard to write it out, I've found. It's something like

$$1\cdot 2 + 1\cdot 3 \cdots 1 \cdot p + 2\cdot 3 +2\cdot 4 \cdots (p-1)\cdot p$$,

I believe.

13. Oct 19, 2007

### Dick

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. Oct 19, 2007

### thirdchildikari

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. Oct 19, 2007

### Dick

Don't toy with it. Just do it. 'elementary' means 'not even hard'.

16. Oct 19, 2007

### thirdchildikari

17. Oct 19, 2007

### Dick

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. Oct 19, 2007

### ramsey2879

What is 2*n!/3!(n-3)!

19. Oct 20, 2007

### Gokul43201

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

$$(\sum_1^p n)^2 - \sum_1^p n^2 \equiv 0~(mod~p)$$

for all odd p not divisible by 3.

20. Oct 20, 2007

### Dick

Ah, ha. It looked to me like the sum the OP wanted was
$$\sum_1^{p-1} n(n+1)$$
I don't think I guessed the intended series correctly.