Results 1 to 3 of 3

Thread: 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 $\displaystyle p$ be prime number:

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

    or:


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


    Proof:

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

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

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

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

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

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

    Hence:

    $\displaystyle 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; Aug 16th 2010 at 07:26 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148
    For $\displaystyle 1^n+2^n+...+(p-1)^n\equiv 0 (\bmod p) $ if $\displaystyle (p-1)\nmid{n} $, you should also add that $\displaystyle 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: Mar 9th 2011, 10:13 PM
  2. x^7 = 12 mod 29 (primitive roots)
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Apr 23rd 2010, 06:57 PM
  3. primitive roots
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Feb 24th 2010, 05:17 AM
  4. Primitive roots
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: May 6th 2008, 09:00 AM
  5. Primitive Roots
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 1st 2007, 07:41 PM

Search Tags


/mathhelpforum @mathhelpforum