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.1k21533




11.1k21533










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

        8771417




        8771417















            Popular posts from this blog

            Bundesstraße 106

            Verónica Boquete

            Ida-Boy-Ed-Garten