Results 1 to 9 of 9

Math Help - About sum of residues

  1. #1
    Member
    Joined
    May 2009
    Posts
    77

    About sum of residues

    Hi everybody
    First of all thank you for your time and your response.

    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
    Last edited by gdmath; May 18th 2009 at 08:34 AM. Reason: mistake on a type: kp-1 actually k(p-1)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    409

    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.
    Last edited by Media_Man; May 18th 2009 at 10:01 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    May 2009
    Posts
    77
    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

    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???
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    May 2009
    Posts
    77
    ans s is positive integer
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    409

    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?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    May 2009
    Posts
    77
    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
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Let g be a primitive root module p. Then <br />
\sum\limits_{k = 1}^{p - 1} {k^s }  \equiv \sum\limits_{k = 0}^{p - 2} {\left( {g^k } \right)^s } \left( {\bmod .p} \right)<br />


    • 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 <br />
\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)<br />
hence -by (*)- <br />
\sum\limits_{k = 0}^{p - 2} {g^{s \cdot k} }  \equiv 0\left( {\bmod .p} \right)<br />


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

    And from there you can easily get your sum MOD. p
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    May 2009
    Posts
    77
    Thank you.
    Can you plz give me a web link about info on primite root module p?
    Thank you again
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    May 2009
    Posts
    77
    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?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. residues
    Posted in the Differential Geometry Forum
    Replies: 5
    Last Post: May 7th 2010, 06:18 AM
  2. Set of residues
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 29th 2009, 09:10 AM
  3. residues
    Posted in the Calculus Forum
    Replies: 6
    Last Post: February 11th 2009, 09:44 AM
  4. residues 2
    Posted in the Calculus Forum
    Replies: 4
    Last Post: February 10th 2009, 09:19 AM
  5. Residues
    Posted in the Calculus Forum
    Replies: 2
    Last Post: November 6th 2008, 10:29 AM

Search Tags


/mathhelpforum @mathhelpforum