- #1
b1029384756
- 15
- 0
I'm trying to help a friend solve a problem but as I've never studied number theory, I'm having a bit of trouble myself figuring out how to do it.
We need to find the sum of 1[tex]^{k}[/tex]+2[tex]^{k}[/tex]+...+(p-1)[tex]^{k}[/tex] (mod p), where p is prime. By writing a program that created a table from test cases 2[tex]\leq[/tex]p[tex]\leq[/tex]47 and 1[tex]\leq[/tex]k[tex]\leq[/tex]100, I've conjectured that if p-1 divides k, the sum is p-1 mod p, and if p-1 does not divide k, the sum is 0 mod p. I need to be able to prove this but am not sure how. For the first case, if 1[tex]\leq[/tex]a[tex]\leq[/tex]p-1, then a[tex]^{k}[/tex]=(a[tex]^{p-1}[/tex])[tex]^{n}[/tex] for some n, which is congruent to 1[tex]^{n}[/tex] by Fermat's little theorem, so then it is congruent to 1. Since there are p-1 such terms congruent to 1, their sum is p-1. Let me know if I've done something incorrectly.
As for the second case where p-1 does not divide k, I have no idea how to show that the sum is congruent to 0. Any information is appreciated.
We need to find the sum of 1[tex]^{k}[/tex]+2[tex]^{k}[/tex]+...+(p-1)[tex]^{k}[/tex] (mod p), where p is prime. By writing a program that created a table from test cases 2[tex]\leq[/tex]p[tex]\leq[/tex]47 and 1[tex]\leq[/tex]k[tex]\leq[/tex]100, I've conjectured that if p-1 divides k, the sum is p-1 mod p, and if p-1 does not divide k, the sum is 0 mod p. I need to be able to prove this but am not sure how. For the first case, if 1[tex]\leq[/tex]a[tex]\leq[/tex]p-1, then a[tex]^{k}[/tex]=(a[tex]^{p-1}[/tex])[tex]^{n}[/tex] for some n, which is congruent to 1[tex]^{n}[/tex] by Fermat's little theorem, so then it is congruent to 1. Since there are p-1 such terms congruent to 1, their sum is p-1. Let me know if I've done something incorrectly.
As for the second case where p-1 does not divide k, I have no idea how to show that the sum is congruent to 0. Any information is appreciated.