• May 18th 2009, 03:00 AM
gdmath
Hi everybody

I encountered the following issue:

sm=Sum( n^s % p, {n,1,p-2} )

(Where % = modulo, p is prime, s is a positive integer)

Is there any proof thats shows:

sm % p= 0 for odd s
sm % p= -1 for even s
sm % p = -2 for s = k(p-1) where k any integer greater than 1

If there is plz tell me
I give you the mathematica commands,
I used for this issue:

p = 11
s = 8
sm = 0
Do[{f = Mod[n^s, p], sm = sm + f}, {n, 1, p - 2}]
Mod[sm, p]

Thank you again
• May 18th 2009, 08:50 AM
Media_Man
So we're all sprickety the same lingity...
You're asking for a proof or counterexample for the following:

Define $f_p:\mathbb{N} \rightarrow\mathbb{N}$ by $f_p(s)=\sum_{n=1}^{p-2} n^s$ for some prime $p$

Theorem:

(i) $f_p(s) \equiv 0 (\bmod p)$ when $s$ is even
(ii) $f_p(s) \equiv -1 (\bmod p)$ when $s$ is odd
(iii) $f_p(s) \equiv -2 (\bmod p)$ when $s$ is of the form $k(p-1)$ for some integer $k > 1$

Is this correct? ***I think I may be misinterpreting you, as this theorem as I have written it is very wrong.
• May 18th 2009, 10:11 AM
gdmath
Yes that exactly i want, either a solution or a counter example.

Forgive me about the inconvenient notation
but i am just a computer guy using math (Itwasntme)

However i used binomial theorem expansion and I THINK that the following is correct:

p is prime, % is modulo operator

From binomial expansion we have:
Sum[n^s, {n,1,p-1}] % p = 0 (right? - i saw its expansion in wikipedia)

Anyway this can be also written:
(1^s % p + 2^s % p+...+(p-1)^s%p)%p=0
Now if we substuct the last term (which its modulo is -1 or 1 depends from even or odd s), we can have some results.

Right or... wrong???
• May 18th 2009, 10:16 AM
gdmath
ans s is positive integer
• May 18th 2009, 10:33 AM
Media_Man
Example
According to my definition...

$f_{11}(8)=1^8+2^8+3^8+4^8+5^8+6^8+7^8+8^8+9^8=6773 1333 \equiv -1 (\bmod 11)$

Did you switch (i) and (ii) by accident?
• May 18th 2009, 11:12 AM
gdmath
You mean in my last reply.
Indeed, sorry, I just gave you a proof skech. The complete proof (i do not actualy care about a strct proof with explicit mathematical notation) i work on it. As soon as i have it I type it in this thread.

IF you think that using binomial coeficient for the proof is false,
or you see something else false plz TELL ME.

Anyway i have made one more mistake in the initial assumtion

So the correct is:

sm=Sum( n^s % p, {n,1,p-2} )
(Where % = modulo, p is prime, s is a positive integer)
Is there any proof thats shows:
sm % p= 1 for odd s
sm % p= -1 for even s
sm % p = -2 for s = k(p-1) where k any integer greater than 1
• May 18th 2009, 11:22 AM
PaulRS
Let $g$ be a primitive root module $p$. Then $
\sum\limits_{k = 1}^{p - 1} {k^s } \equiv \sum\limits_{k = 0}^{p - 2} {\left( {g^k } \right)^s } \left( {\bmod .p} \right)
$

• If $(p-1)|s$ it follows that: $\left( {g^k } \right)^s = g^{k \cdot s} \equiv 1\left( {\bmod .p} \right)$ thus: $\sum\limits_{k = 1}^{p - 1} {k^s } \equiv \sum\limits_{k = 0}^{p - 2} {1 } \left( {\bmod .p} \right)$ i.e. $\sum\limits_{k = 1}^{p - 1} {k^s } \equiv (p-1)\equiv -1 \left( {\bmod .p} \right)$
• If $(p-1)\not |s$ then: $p\not | (g^s -1)$ (*) but note that $
\left( {g^s - 1} \right) \cdot \sum\limits_{k = 0}^{p - 2} {\left( {g^s } \right)^k } = g^{\left( {p - 1} \right) \cdot s} - 1 \equiv 0\left( {\bmod .p} \right)
$
hence -by (*)- $
\sum\limits_{k = 0}^{p - 2} {g^{s \cdot k} } \equiv 0\left( {\bmod .p} \right)
$

Thus: $
\sum\limits_{k = 1}^{p - 1} {k^s } \equiv \left\{ \begin{gathered}
- 1\left( {\bmod .p} \right){\text{ when }}\left. {\left( {p - 1} \right)} \right|s \hfill \\
0\left( {\bmod .p} \right){\text{ otherwise}} \hfill \\
\end{gathered} \right.
$

And from there you can easily get your sum MOD. p
• May 18th 2009, 11:33 AM
gdmath
Thank you.
Can you plz give me a web link about info on primite root module p?
Thank you again
• May 18th 2009, 11:54 AM
gdmath
Something last:

The proof above, implies that

Sum[n^s, {n, 1, p-1}]

is not divisible by p when s=k(p-1)

Where p is prime.
The opossite is valid?
eg.
When p is not prime, sum above is always divisible by p?