Register to reply 
Prime congruence series formula 
Share this thread: 
#1
Jun1710, 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]+...+(p1)[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 p1 divides k, the sum is p1 mod p, and if p1 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]p1, then a[tex]^{k}[/tex]=(a[tex]^{p1}[/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 p1 such terms congruent to 1, their sum is p1. Let me know if I've done something incorrectly. As for the second case where p1 does not divide k, I have no idea how to show that the sum is congruent to 0. Any information is appreciated. 


#2
Jun1810, 11:12 AM

P: 361

HTH Petek 


#3
Jun1810, 11:39 AM

P: 15

If the values are distinct, then each of 1, 2, ..., p1 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 p1 is even, and (p1)/2 is an integer. Therefore, (p[tex]^{2}[/tex]p)/2 = p(p1)/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 p1 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
Jun1810, 05:45 PM

P: 361

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 < p1 (r > 0 by hypothesis). Consider n^k. Can you take it from there? 


#5
Jun1810, 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?



#6
Jun1910, 12:04 AM

P: 361

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
Jun1910, 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.



#8
Jun1910, 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](p1)/2. Consider its additive inverse, (pa)[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 (p1)/2 terms, there is a corresponding term in the second (p1)/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](p1)/2. Since p  1 does not divide k, k is not congruent to 0. This time, (pa)[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](p1)/2. I don't know if this is helpful or what to do with it. Let me know what to do. 


#9
Jun1910, 01:37 PM

P: 361

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 nonzero elements of Z/pZ. See this Wikipedia article if you're not familiar with primitive roots. Thus, each of the numbers 1, 2, ..., p1 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^{(p2)k} \ (mod\ p)[/tex] The RHS of this equation is a geometric series that equals [tex]\frac{1  g^{(p1)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^{(p1)k} \equiv 1\ (mod\ p)[/itex] and so the sum is divisible by p, as required. Hope this is correct. Petek 


#10
Jun1910, 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 