Sums of natural numbers to p and subsequent divisibility

In summary: I see what you're getting at.Yes. The coefficient of x^(p-2) is the sum of the products of ALL unequal pairs of integers between 1 and p.
  • #1
thirdchildikari
17
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]

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?
 
Physics news on Phys.org
  • #2
In retrospect, this post may not belong in this particular sub forum, as it does relate to a course I'm taking.
 
  • #3
thirdchildikari said:
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
HallsofIvy said:
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
thirdchildikari said:
[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
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
Kreizhn said:
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
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
morphism said:
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
Dick said:
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
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
Dick said:
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
thirdchildikari said:
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
Dick said:
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
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
thirdchildikari said:
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
Dick said:
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
Gokul43201 said:
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
You had it right in post #11. That's the sum I checked.
 
  • #22
In reference to post 16, he hasnt even said sorry, why are we still helping him..
 
  • #23
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.
 

1. What is the definition of "Sums of natural numbers to p and subsequent divisibility"?

The sum of natural numbers to p refers to the addition of all natural numbers from 1 to p, where p is a positive integer. Subsequent divisibility means that the resulting sum is divisible by another number, usually a prime number.

2. Why is studying sums of natural numbers to p and subsequent divisibility important?

Studying sums of natural numbers and their divisibility properties is important in number theory, which is a fundamental branch of mathematics. It helps us understand the relationships between numbers and can lead to new discoveries and insights in other areas of mathematics.

3. What is the formula for finding the sum of natural numbers to p?

The formula for the sum of natural numbers to p is (p * (p + 1)) / 2. This is known as the Gauss formula and can be used to quickly calculate the sum without having to manually add each individual number.

4. How can we determine if the sum of natural numbers to p is divisible by a specific number?

If the sum of natural numbers to p is divisible by a number, then the remainder when the sum is divided by that number will be 0. For example, if the sum is divisible by 3, then the remainder is 0 when the sum is divided by 3.

5. How are sums of natural numbers to p and subsequent divisibility used in real-life applications?

Sums of natural numbers to p and subsequent divisibility have various real-life applications, such as in cryptography, coding theory, and computer science. They can also be used to solve problems in economics, physics, and other fields that involve mathematical modeling.

Similar threads

  • Calculus and Beyond Homework Help
Replies
3
Views
681
  • Calculus and Beyond Homework Help
Replies
1
Views
614
  • Calculus and Beyond Homework Help
Replies
24
Views
617
  • Calculus and Beyond Homework Help
Replies
10
Views
1K
Replies
23
Views
1K
  • Precalculus Mathematics Homework Help
Replies
17
Views
2K
  • Calculus and Beyond Homework Help
Replies
5
Views
922
  • Calculus and Beyond Homework Help
Replies
4
Views
2K
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
Replies
5
Views
839
Back
Top