# powers modulo p and primitive root question

Printable View

• Jun 14th 2008, 07:45 AM
duggaboy
powers modulo p and primitive root question
Let p be a prime number.
What is the value of 1 + 2 + 3 +......+(p-1) (mod p)

How would I begin to work this problem?
• Jun 14th 2008, 08:26 AM
Isomorphism
Quote:

Originally Posted by duggaboy
Let p be a prime number.
What is the value of 1 + 2 + 3 +......+(p-1) (mod p)

How would I begin to work this problem?

Note that (p-k) = -k mod p, k = 1,2,3,4,...

1 + 2 + 3 +......+(p-1) (mod p) = 1 + (p-1)+ 2 + (p-2) +......+(p-1)/2 + (p+1)/2 (mod p) = p + p +......+p (mod p) = 0
• Jun 14th 2008, 08:57 AM
duggaboy
ok is the idea here that p + p +...+p (modp) =0 because the modulo and the prime number are the same its always eqaul to zero? I'm a little confused why we want it to equal 0....

Thank you so very much : )
• Jun 14th 2008, 09:00 AM
Isomorphism
Quote:

Originally Posted by duggaboy
ok is the idea here that p + p +...+p (modp) =0 because the modulo and the prime number are the same its always eqaul to zero? I'm a little confused why we want it to equal 0....

Thank you so very much : )

Ya you are right!

p mod p = 0 is the reason
• Jun 14th 2008, 06:02 PM
ThePerfectHacker
Quote:

Originally Posted by duggaboy
Let p be a prime number.
What is the value of 1 + 2 + 3 +......+(p-1) (mod p)

How would I begin to work this problem?

There is another way: $\displaystyle 1+2+...+(p-1) = p\cdot \tfrac{p-1}{2}$, if $\displaystyle p$ is odd.
And so this is a multiple of $\displaystyle p$ thus it reduces to $\displaystyle 0$ mod $\displaystyle p$.
If $\displaystyle p$ is even then it reduces to $\displaystyle 1$.

Try a harder problem: find $\displaystyle 1^k+2^k+...+(p-1)^k (\bmod p)$ where $\displaystyle k$ is positive integer.
• Jun 16th 2008, 09:57 AM
duggaboy
ok....so if k =2 then we it would be....

1^2 + 2^2 + 3^2 +....+(p-1)^2

(p-1)(p+1)/2p ??

Or would you have to use another approach?? Ultimately you still want 0 mod p right?
• Jun 16th 2008, 10:13 AM
ThePerfectHacker
Quote:

Originally Posted by duggaboy
ok....so if k =2 then we it would be....

1^2 + 2^2 + 3^2 +....+(p-1)^2

(p-1)(p+1)/2p ??

Or would you have to use another approach?? Ultimately you still want 0 mod p right?

I am not exactly sure what you are doing.
Here is a hint, $\displaystyle p$ as a primitive root $\displaystyle a$ and so $\displaystyle \{ 1,2,...,p-1\} = \{ a,a^2,...,a^{p-1} \}$.
• Jun 16th 2008, 10:57 AM
duggaboy
n n n
phi(p) = (p - 1) * p 1 * (p - 1) * p 2 ... (p - 1) * p k
1 1 2 2 k k

phi(p) = p-1.

Somthing like this? to get 0 mod p
how would you handle this one? I am very interested in findining out