Prime congruence series formula

In summary, the goal is to find the sum of 1^{k}+2^{k}+...+(p-1)^{k} (mod p), where p is prime. By creating a table from test cases 2\leqp\leq47 and 1\leqk\leq100, it has been 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. To prove this, it is shown that the values of 1, 2, ..., p-1 are distinct mod p and that the sum equals 0 when p-1 does not divide k. To
  • #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.
 
Physics news on Phys.org
  • #2
b1029384756 said:
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
 
  • #3
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.
 
  • #4
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
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
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
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
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.
 
  • #9
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
 
  • #10
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.
 

1. What is the prime congruence series formula?

The prime congruence series formula is a mathematical formula that calculates the sum of a series of prime numbers that follow a specific congruence condition. It is written as P(n) = (p + q) / 2, where n is the number of primes in the series, p and q are the first and last prime numbers in the series, respectively.

2. How is the prime congruence series formula derived?

The prime congruence series formula is derived using number theory and the concept of modular arithmetic. It is based on the theorem that states that the sum of consecutive prime numbers is always a multiple of the number of primes in the series plus one.

3. What is the significance of the prime congruence series formula?

The prime congruence series formula has significance in number theory and cryptography. It is used to generate secure prime numbers for encryption algorithms, as well as to study the distribution of prime numbers and their patterns.

4. Can the prime congruence series formula be applied to non-prime numbers?

No, the prime congruence series formula only applies to series of prime numbers that follow a specific congruence condition. It cannot be applied to series of non-prime numbers or prime numbers that do not meet the congruence condition.

5. Are there any limitations to the prime congruence series formula?

Yes, the prime congruence series formula has limitations in terms of the size and range of prime numbers it can calculate. It is also limited to series of prime numbers that meet the congruence condition, and cannot be used for other types of mathematical series.

Similar threads

  • Linear and Abstract Algebra
Replies
17
Views
1K
  • Linear and Abstract Algebra
Replies
2
Views
882
  • Precalculus Mathematics Homework Help
Replies
17
Views
2K
  • Linear and Abstract Algebra
Replies
8
Views
664
  • Linear and Abstract Algebra
Replies
2
Views
912
  • Linear and Abstract Algebra
Replies
17
Views
4K
  • Linear and Abstract Algebra
Replies
28
Views
2K
  • Calculus and Beyond Homework Help
Replies
12
Views
1K
  • Linear and Abstract Algebra
Replies
2
Views
1K
  • Linear and Abstract Algebra
Replies
1
Views
789
Back
Top