Results 1 to 3 of 3

Math Help - 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 \phi(p-1) primitive roots of p is congurent modulo p to  (-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
    9
    Post #5 might help. Assume that p>2.

    Let a_1,a_2,...,a_{\phi(p-1)} be the primitive roots of p. Let a_1 = r then a_2 \equiv r^{b_2} where 1< b_2 < p-1 and \gcd( b_2, p-1)=1. Similarly a_3 \equiv r^{b_3} and so one.
    Thus, r^{1},r^{b_2},...,r^{b_{\phi(p-1)}} are all the primitive roots. Now one of the exponents of r are the same, and they are all relatively prime to p-1. By pigeonholing we see that they are a premutation of all integers relatively prime to p-1 and less than it.
    Thus, 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 c_1+...+c_{\phi(p-1)} where c_1,c_2,...,c_{\phi(p-1)} are all the positive integers less than p-1 and are congruent to p-1 written in increasing order. Note that 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 p-1, thus, c_1+...+c_{\phi(p-1)} = [c_1 - (p-1)]+...+[c_{\phi(p-1)} - (p-1)], thus, c_1+...+c_{\phi(p-1)} = (1/2)(p-1)\phi(p-1).
    Thus, we have,
    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 r^{(p-1)/2} \equiv -1 (\bmod p) (remember that?).
    Thus, 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: July 10th 2011, 05:15 PM
  2. Primitive roots
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: March 9th 2011, 10:13 PM
  3. Replies: 2
    Last Post: December 18th 2009, 12:48 PM
  4. Primitive Roots
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: November 17th 2008, 08:09 PM
  5. [SOLVED] primitive roots problem
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: August 22nd 2008, 11:15 AM

Search Tags


/mathhelpforum @mathhelpforum