# Prime congruence series formula

1. Jun 17, 2010

### 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$$^{k}$$+2$$^{k}$$+...+(p-1)$$^{k}$$ (mod p), where p is prime. By writing a program that created a table from test cases 2$$\leq$$p$$\leq$$47 and 1$$\leq$$k$$\leq$$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$$\leq$$a$$\leq$$p-1, then a$$^{k}$$=(a$$^{p-1}$$)$$^{n}$$ for some n, which is congruent to 1$$^{n}$$ 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.

2. Jun 18, 2010

### 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$$^{k}$$, 2$$^{k}$$, ..., (p - 1)$$^{k}$$ are distinct mod p? If so, what then can you say about the sum?

HTH

Petek

3. Jun 18, 2010

### b1029384756

If the values are distinct, then each of 1, 2, ..., p-1 appears once, so their sum is (p$$^{2}$$-p)/2. If p = 2, then p - 1 = 1 which divides p, so the first case applies. So, p$$\geq$$3. Then, p must be odd, so p-1 is even, and (p-1)/2 is an integer. Therefore, (p$$^{2}$$-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.

4. Jun 18, 2010

### 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?

5. Jun 18, 2010

### 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$$^{k}$$ is congruent to m$$^{r}$$ by using Fermat's little theorem again. I'm trying to show that then m$$^{r}$$$$\neq$$n$$^{r}$$, 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$$^{14}$$ is congruent to 16$$^{14}$$, which are both congruent to 1. What am I missing?

6. Jun 19, 2010

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

7. Jun 19, 2010

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

8. Jun 19, 2010

### 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$$^{k}$$, where a$$\leq$$(p-1)/2. Consider its additive inverse, (p-a)$$^{k}$$. Using the binomial formula, we can show the expanded polynomial is congruent to -a$$^{k}$$, 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$$^{k}$$, where a$$\leq$$(p-1)/2. Since p - 1 does not divide k, k is not congruent to 0. This time, (p-a)$$^{k}$$ is congruent to a$$^{k}$$. So, upon combining like terms, we have the 2*$$\sum$$a$$^{k}$$ for 1$$\leq$$a$$\leq$$(p-1)/2. I don't know if this is helpful or what to do with it. Let me know what to do.

9. Jun 19, 2010

### 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

$$1^{k} + 2^{k} + ... + (p - 1)^{k} \equiv 1^{k} + g^{k} + g^{2k} + ... +g^{(p-2)k} \ (mod\ p)$$

The RHS of this equation is a geometric series that equals

$$\frac{1 - g^{(p-1)k}}{1 - g^{k}}$$

where

$$\frac{1}{1 - g^{k}}$$

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

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

Hope this is correct.

Petek

10. Jun 19, 2010

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