Results 1 to 2 of 2

Thread: 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 $\displaystyle r^{(p-1)} \equiv 1 (\bmod p)$ that means $\displaystyle r^{(p-1)} - 1 \equiv 0 (\bmod p)$ since $\displaystyle p$ is odd we can write $\displaystyle [r^{(p-1)/2} - 1][r^{(p-1)/2} + 1]\equiv 0(\bmod p)$. Now it cannot be $\displaystyle r^{(p-1)/2} \equiv 1(\bmod p)$ because $\displaystyle (p-1)/2 < p$. Thus, the only possibility is that $\displaystyle 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 $\displaystyle r' \equiv r^k (\bmod p)$ where $\displaystyle 1\leq k \leq p-1$. For $\displaystyle r'$ be a primitive root it is necessary and sufficient that $\displaystyle \gcd (k, p-1) = 1$. Now $\displaystyle rr' \equiv rr^k \equiv r^{k+1} (\bmod p)$, now for $\displaystyle rr'$ to be a primitive root it is necessary and sufficient that $\displaystyle \gcd(k+1, p-1) = 1$. But that is impossible because $\displaystyle p-1$ is an even number and among $\displaystyle k,k+1$ one is even by pigeonholing. Thus it impossible for $\displaystyle 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, $\displaystyle r' \not \equiv 0 (\bmod p)$ because $\displaystyle rr'\equiv 1$, thus, $\displaystyle \gcd(r',p)=1$ that means we can write $\displaystyle r' \equiv r^k $ for $\displaystyle 1\leq k \leq p-1$. We have that $\displaystyle rr' \equiv rr^k = r^{k+1} \equiv 1 (\bmod p)$ by hypothesis. That means $\displaystyle k+1 = p-1$ because the order of $\displaystyle r$ is $\displaystyle p-1$ and $\displaystyle k+1\leq p-1$. Thus $\displaystyle k = p-2$, so $\displaystyle \gcd( k , p-1) = 1$ and it means it is a primitive root.
    Last edited by ThePerfectHacker; Dec 15th 2007 at 08:18 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: Oct 19th 2010, 10:50 AM
  2. Replies: 0
    Last Post: Jun 29th 2010, 08:48 AM
  3. [SOLVED] direct proof and proof by contradiction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Feb 27th 2010, 10:07 PM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: Jun 8th 2008, 01: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: Apr 14th 2008, 04:07 PM

Search Tags


/mathhelpforum @mathhelpforum