Prime congruence series formula


by b1029384756
Tags: congruence, formula, prime, series
b1029384756
b1029384756 is offline
#1
Jun17-10, 03:34 PM
P: 15
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.
Phys.Org News Partner Science news on Phys.org
Better thermal-imaging lens from waste sulfur
Hackathon team's GoogolPlex gives Siri extra powers
Bright points in Sun's atmosphere mark patterns deep in its interior
Petek
Petek is offline
#2
Jun18-10, 11:12 AM
Petek's Avatar
P: 360
Quote Quote by b1029384756 View Post
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.
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
b1029384756 is offline
#3
Jun18-10, 11:39 AM
P: 15
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
Petek is offline
#4
Jun18-10, 05:45 PM
Petek's Avatar
P: 360

Prime congruence series formula


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
b1029384756 is offline
#5
Jun18-10, 11:55 PM
P: 15
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
Petek is offline
#6
Jun19-10, 12:04 AM
Petek's Avatar
P: 360
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
b1029384756 is offline
#7
Jun19-10, 12:29 AM
P: 15
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
b1029384756 is offline
#8
Jun19-10, 02:28 AM
P: 15
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
Petek is offline
#9
Jun19-10, 01:37 PM
Petek's Avatar
P: 360
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
b1029384756 is offline
#10
Jun19-10, 02:55 PM
P: 15
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.


Register to reply

Related Discussions
Possible convergence of prime series Linear & Abstract Algebra 8
Prime number formula General Math 6
A formula of prime numbers for interval (q; (q+1)^2) Linear & Abstract Algebra 3
A formula of prime numbers for interval (q; (q+1)^2), where q is prime number. Linear & Abstract Algebra 0
New prime series? Linear & Abstract Algebra 38