Show that $−g$ is also a primitive root of $p$ if $pequiv 1 pmod{4}$, but that $ord_p(−g) =...












1












$begingroup$



This question already has an answer here:




  • When g and -g are both primitive roots

    2 answers




Let $p$ be an odd prime and let $g$ be a primitive root $pmod{p}$.
Show that $−g$ is also a primitive root of $p$ if $p equiv 1 pmod{4}$, but that $ord_p(−g) = frac{p−1}{2}$ if $p equiv 3 pmod{4}$.



So far, I have shown as $p equiv1 pmod{4}$ I can use Fermat's Little Theorem.
$$g equiv g^{p} equiv -(-g)^{p} pmod{p}$$



Since $p equiv 1 pmod{4}$, $x^2 equiv -1 pmod{p}$. ($-1$ is a QR of $p$)
There $exists k in mathbb{Z}$ such that



$$-1 equiv g^{2k} equiv (-g)^{2k} pmod{p}$$



Thus, $g equiv (-g)^{2k}(-g)^{p} pmod{p}$.
As $g$ is congruent to $-g^{p}$, $-g$ is a primitive root of $p$.



Is this enough to show the first part of the question, also how do I begin to show the 2nd part?










share|cite|improve this question











$endgroup$



marked as duplicate by user10354138, user593746, Jyrki Lahtonen, Kevin, José Carlos Santos Dec 13 '18 at 15:09


This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.














  • 1




    $begingroup$
    math.stackexchange.com/questions/1229270/…
    $endgroup$
    – lab bhattacharjee
    Dec 11 '18 at 11:43






  • 1




    $begingroup$
    Find a way to write -1 as a power of the primitive root g then use the fact that $text{ord}_p(g^d) = frac{text{ord}_p(g)}{text{gcd}(text{ord}_p(g),d)}$. That is, find the gcd$(text{ord}_p(g),d)$, where $-g equiv g^d text{mod }p$ and the result will follow.
    $endgroup$
    – user337254
    Dec 11 '18 at 15:28
















1












$begingroup$



This question already has an answer here:




  • When g and -g are both primitive roots

    2 answers




Let $p$ be an odd prime and let $g$ be a primitive root $pmod{p}$.
Show that $−g$ is also a primitive root of $p$ if $p equiv 1 pmod{4}$, but that $ord_p(−g) = frac{p−1}{2}$ if $p equiv 3 pmod{4}$.



So far, I have shown as $p equiv1 pmod{4}$ I can use Fermat's Little Theorem.
$$g equiv g^{p} equiv -(-g)^{p} pmod{p}$$



Since $p equiv 1 pmod{4}$, $x^2 equiv -1 pmod{p}$. ($-1$ is a QR of $p$)
There $exists k in mathbb{Z}$ such that



$$-1 equiv g^{2k} equiv (-g)^{2k} pmod{p}$$



Thus, $g equiv (-g)^{2k}(-g)^{p} pmod{p}$.
As $g$ is congruent to $-g^{p}$, $-g$ is a primitive root of $p$.



Is this enough to show the first part of the question, also how do I begin to show the 2nd part?










share|cite|improve this question











$endgroup$



marked as duplicate by user10354138, user593746, Jyrki Lahtonen, Kevin, José Carlos Santos Dec 13 '18 at 15:09


This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.














  • 1




    $begingroup$
    math.stackexchange.com/questions/1229270/…
    $endgroup$
    – lab bhattacharjee
    Dec 11 '18 at 11:43






  • 1




    $begingroup$
    Find a way to write -1 as a power of the primitive root g then use the fact that $text{ord}_p(g^d) = frac{text{ord}_p(g)}{text{gcd}(text{ord}_p(g),d)}$. That is, find the gcd$(text{ord}_p(g),d)$, where $-g equiv g^d text{mod }p$ and the result will follow.
    $endgroup$
    – user337254
    Dec 11 '18 at 15:28














1












1








1


1



$begingroup$



This question already has an answer here:




  • When g and -g are both primitive roots

    2 answers




Let $p$ be an odd prime and let $g$ be a primitive root $pmod{p}$.
Show that $−g$ is also a primitive root of $p$ if $p equiv 1 pmod{4}$, but that $ord_p(−g) = frac{p−1}{2}$ if $p equiv 3 pmod{4}$.



So far, I have shown as $p equiv1 pmod{4}$ I can use Fermat's Little Theorem.
$$g equiv g^{p} equiv -(-g)^{p} pmod{p}$$



Since $p equiv 1 pmod{4}$, $x^2 equiv -1 pmod{p}$. ($-1$ is a QR of $p$)
There $exists k in mathbb{Z}$ such that



$$-1 equiv g^{2k} equiv (-g)^{2k} pmod{p}$$



Thus, $g equiv (-g)^{2k}(-g)^{p} pmod{p}$.
As $g$ is congruent to $-g^{p}$, $-g$ is a primitive root of $p$.



Is this enough to show the first part of the question, also how do I begin to show the 2nd part?










share|cite|improve this question











$endgroup$





This question already has an answer here:




  • When g and -g are both primitive roots

    2 answers




Let $p$ be an odd prime and let $g$ be a primitive root $pmod{p}$.
Show that $−g$ is also a primitive root of $p$ if $p equiv 1 pmod{4}$, but that $ord_p(−g) = frac{p−1}{2}$ if $p equiv 3 pmod{4}$.



So far, I have shown as $p equiv1 pmod{4}$ I can use Fermat's Little Theorem.
$$g equiv g^{p} equiv -(-g)^{p} pmod{p}$$



Since $p equiv 1 pmod{4}$, $x^2 equiv -1 pmod{p}$. ($-1$ is a QR of $p$)
There $exists k in mathbb{Z}$ such that



$$-1 equiv g^{2k} equiv (-g)^{2k} pmod{p}$$



Thus, $g equiv (-g)^{2k}(-g)^{p} pmod{p}$.
As $g$ is congruent to $-g^{p}$, $-g$ is a primitive root of $p$.



Is this enough to show the first part of the question, also how do I begin to show the 2nd part?





This question already has an answer here:




  • When g and -g are both primitive roots

    2 answers








number-theory prime-numbers modular-arithmetic primitive-roots






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Dec 13 '18 at 8:07









rtybase

11.5k31534




11.5k31534










asked Dec 11 '18 at 11:28









frankfieldsfrankfields

165




165




marked as duplicate by user10354138, user593746, Jyrki Lahtonen, Kevin, José Carlos Santos Dec 13 '18 at 15:09


This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.









marked as duplicate by user10354138, user593746, Jyrki Lahtonen, Kevin, José Carlos Santos Dec 13 '18 at 15:09


This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.










  • 1




    $begingroup$
    math.stackexchange.com/questions/1229270/…
    $endgroup$
    – lab bhattacharjee
    Dec 11 '18 at 11:43






  • 1




    $begingroup$
    Find a way to write -1 as a power of the primitive root g then use the fact that $text{ord}_p(g^d) = frac{text{ord}_p(g)}{text{gcd}(text{ord}_p(g),d)}$. That is, find the gcd$(text{ord}_p(g),d)$, where $-g equiv g^d text{mod }p$ and the result will follow.
    $endgroup$
    – user337254
    Dec 11 '18 at 15:28














  • 1




    $begingroup$
    math.stackexchange.com/questions/1229270/…
    $endgroup$
    – lab bhattacharjee
    Dec 11 '18 at 11:43






  • 1




    $begingroup$
    Find a way to write -1 as a power of the primitive root g then use the fact that $text{ord}_p(g^d) = frac{text{ord}_p(g)}{text{gcd}(text{ord}_p(g),d)}$. That is, find the gcd$(text{ord}_p(g),d)$, where $-g equiv g^d text{mod }p$ and the result will follow.
    $endgroup$
    – user337254
    Dec 11 '18 at 15:28








1




1




$begingroup$
math.stackexchange.com/questions/1229270/…
$endgroup$
– lab bhattacharjee
Dec 11 '18 at 11:43




$begingroup$
math.stackexchange.com/questions/1229270/…
$endgroup$
– lab bhattacharjee
Dec 11 '18 at 11:43




1




1




$begingroup$
Find a way to write -1 as a power of the primitive root g then use the fact that $text{ord}_p(g^d) = frac{text{ord}_p(g)}{text{gcd}(text{ord}_p(g),d)}$. That is, find the gcd$(text{ord}_p(g),d)$, where $-g equiv g^d text{mod }p$ and the result will follow.
$endgroup$
– user337254
Dec 11 '18 at 15:28




$begingroup$
Find a way to write -1 as a power of the primitive root g then use the fact that $text{ord}_p(g^d) = frac{text{ord}_p(g)}{text{gcd}(text{ord}_p(g),d)}$. That is, find the gcd$(text{ord}_p(g),d)$, where $-g equiv g^d text{mod }p$ and the result will follow.
$endgroup$
– user337254
Dec 11 '18 at 15:28










1 Answer
1






active

oldest

votes


















0












$begingroup$

First of all, consider this fact:




If $a$ is of order $h$ $pmod n$, then $a^k$ is of order $frac{h}{gcd(h,k)} quad quad quadquad quad (1)$




The Proof:



Since $g$ is a primitive root, $-1 equiv g^{frac{p-1}{2}} pmod p$. Therefore, $-g equiv (-1)(g) equiv g^{frac{p-1}{2}}g equiv g^{frac{p+1}{2}} pmod p$. Now, the order of $g^{frac{p+1}{2}} pmod p$ according to $(1)$ is $frac{p-1}{gcd(frac{p+1}{2},p-1)}$. If $pequiv 1 pmod 4$, then $frac{p+1}{2}$ is odd and ${gcd(frac{p+1}{2},p-1)}$ is 1 making the order of $-g$ to be $p-1$. i.e. a primitive root. Otherwise, the term $frac{p+1}{2}$ is even and ${gcd(frac{p+1}{2},p-1)} = frac{p-1}{2} > 1$. Therefore, the order of $-g$ is not $p-1$. i.e. not a primitive root.



I am quoting my answer on my question here with some minor changes.






share|cite|improve this answer









$endgroup$




















    1 Answer
    1






    active

    oldest

    votes








    1 Answer
    1






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    0












    $begingroup$

    First of all, consider this fact:




    If $a$ is of order $h$ $pmod n$, then $a^k$ is of order $frac{h}{gcd(h,k)} quad quad quadquad quad (1)$




    The Proof:



    Since $g$ is a primitive root, $-1 equiv g^{frac{p-1}{2}} pmod p$. Therefore, $-g equiv (-1)(g) equiv g^{frac{p-1}{2}}g equiv g^{frac{p+1}{2}} pmod p$. Now, the order of $g^{frac{p+1}{2}} pmod p$ according to $(1)$ is $frac{p-1}{gcd(frac{p+1}{2},p-1)}$. If $pequiv 1 pmod 4$, then $frac{p+1}{2}$ is odd and ${gcd(frac{p+1}{2},p-1)}$ is 1 making the order of $-g$ to be $p-1$. i.e. a primitive root. Otherwise, the term $frac{p+1}{2}$ is even and ${gcd(frac{p+1}{2},p-1)} = frac{p-1}{2} > 1$. Therefore, the order of $-g$ is not $p-1$. i.e. not a primitive root.



    I am quoting my answer on my question here with some minor changes.






    share|cite|improve this answer









    $endgroup$


















      0












      $begingroup$

      First of all, consider this fact:




      If $a$ is of order $h$ $pmod n$, then $a^k$ is of order $frac{h}{gcd(h,k)} quad quad quadquad quad (1)$




      The Proof:



      Since $g$ is a primitive root, $-1 equiv g^{frac{p-1}{2}} pmod p$. Therefore, $-g equiv (-1)(g) equiv g^{frac{p-1}{2}}g equiv g^{frac{p+1}{2}} pmod p$. Now, the order of $g^{frac{p+1}{2}} pmod p$ according to $(1)$ is $frac{p-1}{gcd(frac{p+1}{2},p-1)}$. If $pequiv 1 pmod 4$, then $frac{p+1}{2}$ is odd and ${gcd(frac{p+1}{2},p-1)}$ is 1 making the order of $-g$ to be $p-1$. i.e. a primitive root. Otherwise, the term $frac{p+1}{2}$ is even and ${gcd(frac{p+1}{2},p-1)} = frac{p-1}{2} > 1$. Therefore, the order of $-g$ is not $p-1$. i.e. not a primitive root.



      I am quoting my answer on my question here with some minor changes.






      share|cite|improve this answer









      $endgroup$
















        0












        0








        0





        $begingroup$

        First of all, consider this fact:




        If $a$ is of order $h$ $pmod n$, then $a^k$ is of order $frac{h}{gcd(h,k)} quad quad quadquad quad (1)$




        The Proof:



        Since $g$ is a primitive root, $-1 equiv g^{frac{p-1}{2}} pmod p$. Therefore, $-g equiv (-1)(g) equiv g^{frac{p-1}{2}}g equiv g^{frac{p+1}{2}} pmod p$. Now, the order of $g^{frac{p+1}{2}} pmod p$ according to $(1)$ is $frac{p-1}{gcd(frac{p+1}{2},p-1)}$. If $pequiv 1 pmod 4$, then $frac{p+1}{2}$ is odd and ${gcd(frac{p+1}{2},p-1)}$ is 1 making the order of $-g$ to be $p-1$. i.e. a primitive root. Otherwise, the term $frac{p+1}{2}$ is even and ${gcd(frac{p+1}{2},p-1)} = frac{p-1}{2} > 1$. Therefore, the order of $-g$ is not $p-1$. i.e. not a primitive root.



        I am quoting my answer on my question here with some minor changes.






        share|cite|improve this answer









        $endgroup$



        First of all, consider this fact:




        If $a$ is of order $h$ $pmod n$, then $a^k$ is of order $frac{h}{gcd(h,k)} quad quad quadquad quad (1)$




        The Proof:



        Since $g$ is a primitive root, $-1 equiv g^{frac{p-1}{2}} pmod p$. Therefore, $-g equiv (-1)(g) equiv g^{frac{p-1}{2}}g equiv g^{frac{p+1}{2}} pmod p$. Now, the order of $g^{frac{p+1}{2}} pmod p$ according to $(1)$ is $frac{p-1}{gcd(frac{p+1}{2},p-1)}$. If $pequiv 1 pmod 4$, then $frac{p+1}{2}$ is odd and ${gcd(frac{p+1}{2},p-1)}$ is 1 making the order of $-g$ to be $p-1$. i.e. a primitive root. Otherwise, the term $frac{p+1}{2}$ is even and ${gcd(frac{p+1}{2},p-1)} = frac{p-1}{2} > 1$. Therefore, the order of $-g$ is not $p-1$. i.e. not a primitive root.



        I am quoting my answer on my question here with some minor changes.







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered Dec 13 '18 at 7:42









        Maged SaeedMaged Saeed

        8921417




        8921417















            Popular posts from this blog

            How to send String Array data to Server using php in android

            Title Spacing in Bjornstrup Chapter, Removing Chapter Number From Contents

            Is anime1.com a legal site for watching anime?