Results 1 to 2 of 2

Math Help - help with proof

  1. #1
    Newbie
    Joined
    Dec 2007
    Posts
    12

    help with proof

    hi every one

    can any one help me to prove the following problem

    Assuming thatr is a primitive root of the odd prime p, establish the following fact

    a) the congruence r^((p-1)/2) =-1(mod p) holds.
    b) if r' is any other primitive root of p , then rr' is not primitive root of p.
    c) if the integer r' is such that rr'=1(mod p) then r' is primitive root of p.

    and thnx alot
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by midosoft View Post
    a) the congruence r^((p-1)/2) =-1(mod p) holds.
    We know r^{(p-1)} \equiv 1 (\bmod p) that means r^{(p-1)} - 1 \equiv 0 (\bmod p) since p is odd we can write [r^{(p-1)/2} - 1][r^{(p-1)/2} + 1]\equiv 0(\bmod p). Now it cannot be r^{(p-1)/2} \equiv 1(\bmod p) because (p-1)/2 < p. Thus, the only possibility is that r^{(p-1)/2} \equiv - 1(\bmod p).
    b) if r' is any other primitive root of p , then rr' is not primitive root of p.
    We can write r' \equiv r^k (\bmod p) where 1\leq k \leq p-1. For r' be a primitive root it is necessary and sufficient that \gcd (k, p-1) = 1. Now rr' \equiv rr^k \equiv r^{k+1} (\bmod p), now for rr' to be a primitive root it is necessary and sufficient that \gcd(k+1, p-1) = 1. But that is impossible because p-1 is an even number and among k,k+1 one is even by pigeonholing. Thus it impossible for rr' to be a primitive root canal.

    c) if the integer r' is such that rr'=1(mod p) then r' is primitive root of p.
    Now, r' \not \equiv 0 (\bmod p) because rr'\equiv 1, thus, \gcd(r',p)=1 that means we can write r' \equiv r^k for 1\leq k \leq p-1. We have that rr' \equiv rr^k = r^{k+1} \equiv 1 (\bmod p) by hypothesis. That means k+1 = p-1 because the order of r is p-1 and k+1\leq p-1. Thus k = p-2, so \gcd( k , p-1) = 1 and it means it is a primitive root.
    Last edited by ThePerfectHacker; December 15th 2007 at 09:18 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: October 19th 2010, 11:50 AM
  2. Replies: 0
    Last Post: June 29th 2010, 09:48 AM
  3. [SOLVED] direct proof and proof by contradiction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 27th 2010, 11:07 PM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 02:20 PM
  5. proof that the proof that .999_ = 1 is not a proof (version)
    Posted in the Advanced Applied Math Forum
    Replies: 4
    Last Post: April 14th 2008, 05:07 PM

Search Tags


/mathhelpforum @mathhelpforum