# Sums of natural numbers to p and subsequent divisibility

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?

Related Calculus and Beyond Homework Help News on Phys.org
In retrospect, this post may not belong in this particular sub forum, as it does relate to a course I'm taking.

HallsofIvy
Homework Helper
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$$.
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. 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$$

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?

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. My mistake, it has to be an odd prime greater than 3. morphism Science Advisor Homework Helper [tex]x^p - x \equiv (x-1)(x-2)\cdots (x-p) \bmod p$$
Try to expand the right side to see what the coefficient of x^(p-2) looks like.

Last edited:
Wait...no...that's not right.

Clearly $$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$$

Clearly $$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$$
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?

morphism
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).

Dick
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).
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?

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

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

I believe.

Dick
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.

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.

Dick
Homework Helper
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'.

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

Dick
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.

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$$
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)!

Gokul43201
Staff Emeritus
Gold Member
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)

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

for all odd p not divisible by 3.

Dick
Homework Helper
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.
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.

Gokul43201
Staff Emeritus
Gold Member
You had it right in post #11. That's the sum I checked.

Gib Z
Homework Helper
In reference to post 16, he hasnt even said sorry, why are we still helping him..

Dick