Results 1 to 3 of 3

Thread: problem in primitive roots

  1. #1
    Newbie
    Joined
    Dec 2007
    Posts
    12

    problem in primitive roots

    i wish any one can hepl me with this problems

    1) if p is prime , show that th product of the $\displaystyle \phi(p-1)$ primitive roots of p is congurent modulo p to$\displaystyle (-1)^\phi(p-1)$.

    [hint: if r is primitive root of p , then r^k is primitive root of p provided that gcd(k,p-1)= 1 ]

    **********

    2) use the fact that each prime p has a primitive root to give a different proof of Wislon's theroem.
    [hint : if p has a primitive root r, then (p-1)!=r^1+2+..+(p-1)(modp)]
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Post #5 might help. Assume that p>2.

    Let $\displaystyle a_1,a_2,...,a_{\phi(p-1)}$ be the primitive roots of $\displaystyle p$. Let $\displaystyle a_1 = r$ then $\displaystyle a_2 \equiv r^{b_2}$ where $\displaystyle 1< b_2 < p-1$ and $\displaystyle \gcd( b_2, p-1)=1$. Similarly $\displaystyle a_3 \equiv r^{b_3}$ and so one.
    Thus, $\displaystyle r^{1},r^{b_2},...,r^{b_{\phi(p-1)}}$ are all the primitive roots. Now one of the exponents of $\displaystyle r$ are the same, and they are all relatively prime to $\displaystyle p-1$. By pigeonholing we see that they are a premutation of all integers relatively prime to $\displaystyle p-1$ and less than it.
    Thus, $\displaystyle r^1 \cdot r^{b_2} \cdot ... \cdot r^{ b_{\phi(p-1)}} \equiv r^{c_1+...+c_{\phi(p-1)}} (\bmod p)$.
    The question now is what is a nice formula for $\displaystyle c_1+...+c_{\phi(p-1)}$ where $\displaystyle c_1,c_2,...,c_{\phi(p-1)}$ are all the positive integers less than $\displaystyle p-1$ and are congruent to $\displaystyle p-1$ written in increasing order. Note that $\displaystyle c_1 - (p-1),c_2-(p-1),...,c_{\phi(p-1)} - (p-1)$ all again a permutation of all the relatively prime integers to $\displaystyle p-1$, thus, $\displaystyle c_1+...+c_{\phi(p-1)} = [c_1 - (p-1)]+...+[c_{\phi(p-1)} - (p-1)]$, thus, $\displaystyle c_1+...+c_{\phi(p-1)} = (1/2)(p-1)\phi(p-1)$.
    Thus, we have,
    $\displaystyle r^{c_1+...+c_{\phi(p-1)}} \equiv r^{(1/2)(p-1)\phi(p-1)} \equiv\left( r^{(p-1)/2} \right)^{\phi(p-1)} (\bmod p)$.
    But $\displaystyle r^{(p-1)/2} \equiv -1 (\bmod p)$ (remember that?).
    Thus, $\displaystyle r^{c_1+...+c_{\phi(p-1)}} \equiv (-1)^{\phi(p-1)} (\bmod p)$.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Dec 2007
    Posts
    12
    really thnx man
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Primitive roots
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Jul 10th 2011, 06:15 PM
  2. Primitive roots
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Mar 9th 2011, 11:13 PM
  3. Replies: 2
    Last Post: Dec 18th 2009, 01:48 PM
  4. Primitive Roots
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Nov 17th 2008, 09:09 PM
  5. [SOLVED] primitive roots problem
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: Aug 22nd 2008, 12:15 PM

Search Tags


/mathhelpforum @mathhelpforum