Prime congruence series formula

b1029384756

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.

Petek

Your conjecture is correct, as is your proof of the case in which (p - 1) divides k. For the case in which (p - 1) does not divide k, can you show that the values 1[tex]^{k}[/tex], 2[tex]^{k}[/tex], ..., (p - 1)[tex]^{k}[/tex] are distinct mod p? If so, what then can you say about the sum?

HTH

Petek

b1029384756

If the values are distinct, then each of 1, 2, ..., p-1 appears once, so their sum is (p[tex]^{2}[/tex]-p)/2. If p = 2, then p - 1 = 1 which divides p, so the first case applies. So, p[tex]\geq[/tex]3. Then, p must be odd, so p-1 is even, and (p-1)/2 is an integer. Therefore, (p[tex]^{2}[/tex]-p)/2 = p(p-1)/2 = p*n for some n. This tell us that the sum is zero mod p.

Okay, that part is easy, but I still don't see how to use the fact that p-1 does not divide k to show that the values of each term are distinct. Thanks for the post, let me know what else I'm missing.

Petek

Suppose that (p - 1) does not divide k. Use the Eucidean algorithm to write

k = q(p - 1) + r

where 0 < r < p-1

(r > 0 by hypothesis).

Consider n^k. Can you take it from there?

b1029384756

The problem I have understanding how to do that is...suppose I consider n^k and m^k for distinct m and n. We know that mm[tex]^{k}[/tex] is congruent to m[tex]^{r}[/tex] by using Fermat's little theorem again. I'm trying to show that then m[tex]^{r}[/tex][tex]\neq[/tex]n[tex]^{r}[/tex], correct? But, that's not always the case. Suppose we have p = 29, k = 14, m = 4, n = 16, p - 1 clearly does not divide k, but 4m[tex]^{14}[/tex] is congruent to 16[tex]^{14}[/tex], which are both congruent to 1. What am I missing?

Petek

Sorry, I was wrong. Consider p = 5, k = 2. Then 1 ^2 + 2^2 + 3^2 + 4^4 == 0 (mod 5), but the individual summands aren't distinct mod 5.

b1029384756

So any ideas how else I can prove that the sum will be 0 mod p? I appreciate the attempt, it seemed like a good approach to it.

b1029384756

Okay, I have a step in the right direction. If p - 1 does not divide k, use the argument above to show that p is odd and p - 1 is even. So, there are an even number of terms in the sum.

Suppose k is odd. Then, consider a[tex]^{k}[/tex], where a[tex]\leq[/tex](p-1)/2. Consider its additive inverse, (p-a)[tex]^{k}[/tex]. Using the binomial formula, we can show the expanded polynomial is congruent to -a[tex]^{k}[/tex], because k is odd. So, for each of the first (p-1)/2 terms, there is a corresponding term in the second (p-1)/2 terms to cancel it from the sum, leaving a resulting sum of 0.

Now, how do I show that the sum is 0 when p - 1 does not divide k, and k is even? If this is the case, again consider a[tex]^{k}[/tex], where a[tex]\leq[/tex](p-1)/2. Since p - 1 does not divide k, k is not congruent to 0. This time, (p-a)[tex]^{k}[/tex] is congruent to a[tex]^{k}[/tex]. So, upon combining like terms, we have the 2*[tex]\sum[/tex]a[tex]^{k}[/tex] for 1[tex]\leq[/tex]a[tex]\leq[/tex](p-1)/2. I don't know if this is helpful or what to do with it. Let me know what to do.

Petek

I think I now have a valid solution for the case p - 1 doesn't divide k:

Let g be a primitive root mod p. That is, g generates the multiplicative subgroup that consists of the non-zero elements of Z/pZ. See this Wikipedia article if you're not familiar with primitive roots. Thus, each of the numbers 1, 2, ..., p-1 is congruent to a power of g, mod p. We can then write

[tex]1^{k} + 2^{k} + ... + (p - 1)^{k} \equiv 1^{k} + g^{k} + g^{2k} + ... +g^{(p-2)k} \ (mod\ p)[/tex]

The RHS of this equation is a geometric series that equals

[tex]\frac{1 - g^{(p-1)k}}{1 - g^{k}}[/tex]

where

[tex]\frac{1}{1 - g^{k}}[/tex]

is the multiplicative inverse of [itex]1 - g^{k}[/itex] in Z/pZ. Such an inverse exists because (p - 1) doesn't divide k, and so [itex]g^{k} \not \equiv 1\ (mod\ p)[/itex].

It's easy to see that [itex]g^{(p-1)k} \equiv 1\ (mod\ p)[/itex] and so the sum is divisible by p, as required.

Hope this is correct.

Petek

b1029384756

Thanks, I looked at the article as well as a proof that all primes have at least one primitive root, so now it makes perfect sense. I don't think I would have been able to come up with that on my own without more of a background in number theory, so it's definitely appreciated. I'll explain it to my friend when I see her.