Results 1 to 3 of 3

Math Help - Primitive roots

  1. #1
    Member
    Joined
    May 2008
    Posts
    140

    Primitive roots

    Use primitive roots to prove that


    1^100 + 2^100 + ... +(p-1)^100 = 0 (mod p)

    for all except five primes p. What are these primes?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1
    When 100/(p-1)=t in Z


    then:


    1^100 + 2^100 + ... +(p-1)^100 = -1(mod p)

    So, the primes are:
    2,3,5,11, and... 101

    ================================

    Let p be prime number:

    1^n+2^n+...+(p-1)^n\equiv 0(mod p) if (p-1)\nmid{n}

    or:


    1^n+2^n+...+(p-1)^n\equiv -1(mod p) if (p-1)\mid{n}


    Proof:

    Suppose (p-1)\mid{n} so to every t witch is co-prime to p :

    t^n=(t^{p-1})^{\frac{n}{p-1}}\equiv 1^{\frac{n}{p-1}}\equiv 1(modp)

    Hence, 1^n+2^n+...+(p-1)^n\equiv 1+1+...+1=p-1=-1(modp)

    Now, suppose (p-1)\nmid{n} , and r primitive root of p .

    hence, r,r^2,...,r^{p-1} congruent modulo p to 1,2,...,(p-1) in some order.

    Prove by yourself now that: r^n,r^{2n},...,r^{n(p-1)} is also system of congruent modulo p.

    Hence:

    1^n+2^n+...+(p-1)^n\equiv r^n+r^{2n}+...+r^{n(p-1)}\equiv 1+2+...+(p-1)=\frac{p(p-1)}{2}\equiv 0(modp)
    Last edited by Also sprach Zarathustra; August 16th 2010 at 08:26 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148
    For 1^n+2^n+...+(p-1)^n\equiv 0 (\bmod p) if (p-1)\nmid{n} , you should also add that p is odd.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Primitive roots
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: March 9th 2011, 11:13 PM
  2. x^7 = 12 mod 29 (primitive roots)
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 23rd 2010, 07:57 PM
  3. primitive roots
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 24th 2010, 06:17 AM
  4. Primitive roots
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: May 6th 2008, 10:00 AM
  5. Primitive Roots
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 1st 2007, 08:41 PM

Search Tags


/mathhelpforum @mathhelpforum