Assuming $g$ is a primitive root modulo a prime $p$, show that $p-g$ is a primitive root if and only if $p...












2












$begingroup$



Assume $g$ is a primitive root modulo a prime $p$. Show that $p-g$ is a primitive root if and only if $p equiv 1 pmod 4$.




I am studying for a number theory exam that is why I am posting a lot of questions related to primitive roots. I would really appreciate your help because they seem like really nice questions.










share|cite|improve this question











$endgroup$

















    2












    $begingroup$



    Assume $g$ is a primitive root modulo a prime $p$. Show that $p-g$ is a primitive root if and only if $p equiv 1 pmod 4$.




    I am studying for a number theory exam that is why I am posting a lot of questions related to primitive roots. I would really appreciate your help because they seem like really nice questions.










    share|cite|improve this question











    $endgroup$















      2












      2








      2


      1



      $begingroup$



      Assume $g$ is a primitive root modulo a prime $p$. Show that $p-g$ is a primitive root if and only if $p equiv 1 pmod 4$.




      I am studying for a number theory exam that is why I am posting a lot of questions related to primitive roots. I would really appreciate your help because they seem like really nice questions.










      share|cite|improve this question











      $endgroup$





      Assume $g$ is a primitive root modulo a prime $p$. Show that $p-g$ is a primitive root if and only if $p equiv 1 pmod 4$.




      I am studying for a number theory exam that is why I am posting a lot of questions related to primitive roots. I would really appreciate your help because they seem like really nice questions.







      elementary-number-theory






      share|cite|improve this question















      share|cite|improve this question













      share|cite|improve this question




      share|cite|improve this question








      edited Apr 16 '15 at 4:35









      kate

      5281717




      5281717










      asked Apr 10 '15 at 22:16









      user2214user2214

      1808




      1808






















          2 Answers
          2






          active

          oldest

          votes


















          3












          $begingroup$

          We solve the first problem. The case $p=2$ is simple, so let $p$ be an odd prime.



          If $pequiv 3pmod{4}$, then $p-g$ is not a primitive root of $p$. For $p-gequiv -gpmod{p}$. But $-1$ is a quadratic non-residue of $p$, and therefore $-g$ is a QR of $p$, so cannot be a primitive root of $p$.



          Conversely, let $pequiv 1pmod{4}$. We show that $-g$ is a primitive root of $p$.



          By Fermat's Theorem, $gequiv g^pequiv -(-g)^ppmod{p}$. But $-1$ is a QR of $p$, so $-1equiv g^{2k}equiv (-g)^{2k}pmof{p}$ for some integer $k$.



          t follows that $gequiv (-g)^{2k}(-g)^ppmod{p}$. Thus $g$ is congruent to a power of $-g$. Since the powers of $g$ travel, modulo $p$, through $1,2,dots, p-1$, so do the powers of $-g$, and therefore $-g$ is a primitive root of $p$.



          Remark: For other problems that you may post (and this one also) please indicate what you have tried, any progress you may have made, and where difficulties remain.






          share|cite|improve this answer











          $endgroup$













          • $begingroup$
            Thank you for solving the first question, but I believe I need some help for the 2nd one as well which seems more complicated.So since g is a primitive root mod p that we know that $g^{p-1}=1$ (mod p). We also know that if g is a primitive root then g or g+p is a primitive root of $p^2$.But How do I relate this facts to the 2nd question? @AndreNicolas
            $endgroup$
            – user2214
            Apr 11 '15 at 20:13








          • 1




            $begingroup$
            Your are welcome. Multipart questions in which the parts are not closely related often get closed quickly. I would prefer two questions, the second about primitive roots mod $p^2$. Recall that $g+kp$ is a primitive root mod $p^2$ for all but one $k$ in the interval $0$ to $p-1$.
            $endgroup$
            – André Nicolas
            Apr 11 '15 at 22:34



















          1












          $begingroup$

          $$-g=g(-1)equiv g^{1+(p-1)/2}equiv g^{(p+1)/2}$$



          We know, ord$_ma=d, $ord$_m(a^k)=dfrac d{(d,k)}$ (Proof @Page$#95$)



          ord$_p g^{(p+1)/2}=dfrac{p-1}{left(p-1,dfrac{p+1}2right)}$



          Now, if integer $d(>0)$ divides both, $d$ must divide $-(p-1)+2cdotdfrac{p+1}2=2$



          As for odd prime $p,p-1$ is even



          $left(p-1,dfrac{p+1}2right)=2$ if $dfrac{p+1}2$ is even $=2k$(say) $iff p=4k-1equiv-1pmod4$



          $left(p-1,dfrac{p+1}2right)=1$ if $dfrac{p+1}2$ is odd $=2k+1$(say) $iff p=4k+1equiv1pmod4$






          share|cite|improve this answer









          $endgroup$













          • $begingroup$
            See also: math.stackexchange.com/questions/56028/…
            $endgroup$
            – lab bhattacharjee
            Dec 6 '18 at 11:44











          Your Answer





          StackExchange.ifUsing("editor", function () {
          return StackExchange.using("mathjaxEditing", function () {
          StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
          StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
          });
          });
          }, "mathjax-editing");

          StackExchange.ready(function() {
          var channelOptions = {
          tags: "".split(" "),
          id: "69"
          };
          initTagRenderer("".split(" "), "".split(" "), channelOptions);

          StackExchange.using("externalEditor", function() {
          // Have to fire editor after snippets, if snippets enabled
          if (StackExchange.settings.snippets.snippetsEnabled) {
          StackExchange.using("snippets", function() {
          createEditor();
          });
          }
          else {
          createEditor();
          }
          });

          function createEditor() {
          StackExchange.prepareEditor({
          heartbeatType: 'answer',
          autoActivateHeartbeat: false,
          convertImagesToLinks: true,
          noModals: true,
          showLowRepImageUploadWarning: true,
          reputationToPostImages: 10,
          bindNavPrevention: true,
          postfix: "",
          imageUploader: {
          brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
          contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
          allowUrls: true
          },
          noCode: true, onDemand: true,
          discardSelector: ".discard-answer"
          ,immediatelyShowMarkdownHelp:true
          });


          }
          });














          draft saved

          draft discarded


















          StackExchange.ready(
          function () {
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1229270%2fassuming-g-is-a-primitive-root-modulo-a-prime-p-show-that-p-g-is-a-primit%23new-answer', 'question_page');
          }
          );

          Post as a guest















          Required, but never shown

























          2 Answers
          2






          active

          oldest

          votes








          2 Answers
          2






          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes









          3












          $begingroup$

          We solve the first problem. The case $p=2$ is simple, so let $p$ be an odd prime.



          If $pequiv 3pmod{4}$, then $p-g$ is not a primitive root of $p$. For $p-gequiv -gpmod{p}$. But $-1$ is a quadratic non-residue of $p$, and therefore $-g$ is a QR of $p$, so cannot be a primitive root of $p$.



          Conversely, let $pequiv 1pmod{4}$. We show that $-g$ is a primitive root of $p$.



          By Fermat's Theorem, $gequiv g^pequiv -(-g)^ppmod{p}$. But $-1$ is a QR of $p$, so $-1equiv g^{2k}equiv (-g)^{2k}pmof{p}$ for some integer $k$.



          t follows that $gequiv (-g)^{2k}(-g)^ppmod{p}$. Thus $g$ is congruent to a power of $-g$. Since the powers of $g$ travel, modulo $p$, through $1,2,dots, p-1$, so do the powers of $-g$, and therefore $-g$ is a primitive root of $p$.



          Remark: For other problems that you may post (and this one also) please indicate what you have tried, any progress you may have made, and where difficulties remain.






          share|cite|improve this answer











          $endgroup$













          • $begingroup$
            Thank you for solving the first question, but I believe I need some help for the 2nd one as well which seems more complicated.So since g is a primitive root mod p that we know that $g^{p-1}=1$ (mod p). We also know that if g is a primitive root then g or g+p is a primitive root of $p^2$.But How do I relate this facts to the 2nd question? @AndreNicolas
            $endgroup$
            – user2214
            Apr 11 '15 at 20:13








          • 1




            $begingroup$
            Your are welcome. Multipart questions in which the parts are not closely related often get closed quickly. I would prefer two questions, the second about primitive roots mod $p^2$. Recall that $g+kp$ is a primitive root mod $p^2$ for all but one $k$ in the interval $0$ to $p-1$.
            $endgroup$
            – André Nicolas
            Apr 11 '15 at 22:34
















          3












          $begingroup$

          We solve the first problem. The case $p=2$ is simple, so let $p$ be an odd prime.



          If $pequiv 3pmod{4}$, then $p-g$ is not a primitive root of $p$. For $p-gequiv -gpmod{p}$. But $-1$ is a quadratic non-residue of $p$, and therefore $-g$ is a QR of $p$, so cannot be a primitive root of $p$.



          Conversely, let $pequiv 1pmod{4}$. We show that $-g$ is a primitive root of $p$.



          By Fermat's Theorem, $gequiv g^pequiv -(-g)^ppmod{p}$. But $-1$ is a QR of $p$, so $-1equiv g^{2k}equiv (-g)^{2k}pmof{p}$ for some integer $k$.



          t follows that $gequiv (-g)^{2k}(-g)^ppmod{p}$. Thus $g$ is congruent to a power of $-g$. Since the powers of $g$ travel, modulo $p$, through $1,2,dots, p-1$, so do the powers of $-g$, and therefore $-g$ is a primitive root of $p$.



          Remark: For other problems that you may post (and this one also) please indicate what you have tried, any progress you may have made, and where difficulties remain.






          share|cite|improve this answer











          $endgroup$













          • $begingroup$
            Thank you for solving the first question, but I believe I need some help for the 2nd one as well which seems more complicated.So since g is a primitive root mod p that we know that $g^{p-1}=1$ (mod p). We also know that if g is a primitive root then g or g+p is a primitive root of $p^2$.But How do I relate this facts to the 2nd question? @AndreNicolas
            $endgroup$
            – user2214
            Apr 11 '15 at 20:13








          • 1




            $begingroup$
            Your are welcome. Multipart questions in which the parts are not closely related often get closed quickly. I would prefer two questions, the second about primitive roots mod $p^2$. Recall that $g+kp$ is a primitive root mod $p^2$ for all but one $k$ in the interval $0$ to $p-1$.
            $endgroup$
            – André Nicolas
            Apr 11 '15 at 22:34














          3












          3








          3





          $begingroup$

          We solve the first problem. The case $p=2$ is simple, so let $p$ be an odd prime.



          If $pequiv 3pmod{4}$, then $p-g$ is not a primitive root of $p$. For $p-gequiv -gpmod{p}$. But $-1$ is a quadratic non-residue of $p$, and therefore $-g$ is a QR of $p$, so cannot be a primitive root of $p$.



          Conversely, let $pequiv 1pmod{4}$. We show that $-g$ is a primitive root of $p$.



          By Fermat's Theorem, $gequiv g^pequiv -(-g)^ppmod{p}$. But $-1$ is a QR of $p$, so $-1equiv g^{2k}equiv (-g)^{2k}pmof{p}$ for some integer $k$.



          t follows that $gequiv (-g)^{2k}(-g)^ppmod{p}$. Thus $g$ is congruent to a power of $-g$. Since the powers of $g$ travel, modulo $p$, through $1,2,dots, p-1$, so do the powers of $-g$, and therefore $-g$ is a primitive root of $p$.



          Remark: For other problems that you may post (and this one also) please indicate what you have tried, any progress you may have made, and where difficulties remain.






          share|cite|improve this answer











          $endgroup$



          We solve the first problem. The case $p=2$ is simple, so let $p$ be an odd prime.



          If $pequiv 3pmod{4}$, then $p-g$ is not a primitive root of $p$. For $p-gequiv -gpmod{p}$. But $-1$ is a quadratic non-residue of $p$, and therefore $-g$ is a QR of $p$, so cannot be a primitive root of $p$.



          Conversely, let $pequiv 1pmod{4}$. We show that $-g$ is a primitive root of $p$.



          By Fermat's Theorem, $gequiv g^pequiv -(-g)^ppmod{p}$. But $-1$ is a QR of $p$, so $-1equiv g^{2k}equiv (-g)^{2k}pmof{p}$ for some integer $k$.



          t follows that $gequiv (-g)^{2k}(-g)^ppmod{p}$. Thus $g$ is congruent to a power of $-g$. Since the powers of $g$ travel, modulo $p$, through $1,2,dots, p-1$, so do the powers of $-g$, and therefore $-g$ is a primitive root of $p$.



          Remark: For other problems that you may post (and this one also) please indicate what you have tried, any progress you may have made, and where difficulties remain.







          share|cite|improve this answer














          share|cite|improve this answer



          share|cite|improve this answer








          edited Apr 10 '15 at 22:47

























          answered Apr 10 '15 at 22:40









          André NicolasAndré Nicolas

          452k36425810




          452k36425810












          • $begingroup$
            Thank you for solving the first question, but I believe I need some help for the 2nd one as well which seems more complicated.So since g is a primitive root mod p that we know that $g^{p-1}=1$ (mod p). We also know that if g is a primitive root then g or g+p is a primitive root of $p^2$.But How do I relate this facts to the 2nd question? @AndreNicolas
            $endgroup$
            – user2214
            Apr 11 '15 at 20:13








          • 1




            $begingroup$
            Your are welcome. Multipart questions in which the parts are not closely related often get closed quickly. I would prefer two questions, the second about primitive roots mod $p^2$. Recall that $g+kp$ is a primitive root mod $p^2$ for all but one $k$ in the interval $0$ to $p-1$.
            $endgroup$
            – André Nicolas
            Apr 11 '15 at 22:34


















          • $begingroup$
            Thank you for solving the first question, but I believe I need some help for the 2nd one as well which seems more complicated.So since g is a primitive root mod p that we know that $g^{p-1}=1$ (mod p). We also know that if g is a primitive root then g or g+p is a primitive root of $p^2$.But How do I relate this facts to the 2nd question? @AndreNicolas
            $endgroup$
            – user2214
            Apr 11 '15 at 20:13








          • 1




            $begingroup$
            Your are welcome. Multipart questions in which the parts are not closely related often get closed quickly. I would prefer two questions, the second about primitive roots mod $p^2$. Recall that $g+kp$ is a primitive root mod $p^2$ for all but one $k$ in the interval $0$ to $p-1$.
            $endgroup$
            – André Nicolas
            Apr 11 '15 at 22:34
















          $begingroup$
          Thank you for solving the first question, but I believe I need some help for the 2nd one as well which seems more complicated.So since g is a primitive root mod p that we know that $g^{p-1}=1$ (mod p). We also know that if g is a primitive root then g or g+p is a primitive root of $p^2$.But How do I relate this facts to the 2nd question? @AndreNicolas
          $endgroup$
          – user2214
          Apr 11 '15 at 20:13






          $begingroup$
          Thank you for solving the first question, but I believe I need some help for the 2nd one as well which seems more complicated.So since g is a primitive root mod p that we know that $g^{p-1}=1$ (mod p). We also know that if g is a primitive root then g or g+p is a primitive root of $p^2$.But How do I relate this facts to the 2nd question? @AndreNicolas
          $endgroup$
          – user2214
          Apr 11 '15 at 20:13






          1




          1




          $begingroup$
          Your are welcome. Multipart questions in which the parts are not closely related often get closed quickly. I would prefer two questions, the second about primitive roots mod $p^2$. Recall that $g+kp$ is a primitive root mod $p^2$ for all but one $k$ in the interval $0$ to $p-1$.
          $endgroup$
          – André Nicolas
          Apr 11 '15 at 22:34




          $begingroup$
          Your are welcome. Multipart questions in which the parts are not closely related often get closed quickly. I would prefer two questions, the second about primitive roots mod $p^2$. Recall that $g+kp$ is a primitive root mod $p^2$ for all but one $k$ in the interval $0$ to $p-1$.
          $endgroup$
          – André Nicolas
          Apr 11 '15 at 22:34











          1












          $begingroup$

          $$-g=g(-1)equiv g^{1+(p-1)/2}equiv g^{(p+1)/2}$$



          We know, ord$_ma=d, $ord$_m(a^k)=dfrac d{(d,k)}$ (Proof @Page$#95$)



          ord$_p g^{(p+1)/2}=dfrac{p-1}{left(p-1,dfrac{p+1}2right)}$



          Now, if integer $d(>0)$ divides both, $d$ must divide $-(p-1)+2cdotdfrac{p+1}2=2$



          As for odd prime $p,p-1$ is even



          $left(p-1,dfrac{p+1}2right)=2$ if $dfrac{p+1}2$ is even $=2k$(say) $iff p=4k-1equiv-1pmod4$



          $left(p-1,dfrac{p+1}2right)=1$ if $dfrac{p+1}2$ is odd $=2k+1$(say) $iff p=4k+1equiv1pmod4$






          share|cite|improve this answer









          $endgroup$













          • $begingroup$
            See also: math.stackexchange.com/questions/56028/…
            $endgroup$
            – lab bhattacharjee
            Dec 6 '18 at 11:44
















          1












          $begingroup$

          $$-g=g(-1)equiv g^{1+(p-1)/2}equiv g^{(p+1)/2}$$



          We know, ord$_ma=d, $ord$_m(a^k)=dfrac d{(d,k)}$ (Proof @Page$#95$)



          ord$_p g^{(p+1)/2}=dfrac{p-1}{left(p-1,dfrac{p+1}2right)}$



          Now, if integer $d(>0)$ divides both, $d$ must divide $-(p-1)+2cdotdfrac{p+1}2=2$



          As for odd prime $p,p-1$ is even



          $left(p-1,dfrac{p+1}2right)=2$ if $dfrac{p+1}2$ is even $=2k$(say) $iff p=4k-1equiv-1pmod4$



          $left(p-1,dfrac{p+1}2right)=1$ if $dfrac{p+1}2$ is odd $=2k+1$(say) $iff p=4k+1equiv1pmod4$






          share|cite|improve this answer









          $endgroup$













          • $begingroup$
            See also: math.stackexchange.com/questions/56028/…
            $endgroup$
            – lab bhattacharjee
            Dec 6 '18 at 11:44














          1












          1








          1





          $begingroup$

          $$-g=g(-1)equiv g^{1+(p-1)/2}equiv g^{(p+1)/2}$$



          We know, ord$_ma=d, $ord$_m(a^k)=dfrac d{(d,k)}$ (Proof @Page$#95$)



          ord$_p g^{(p+1)/2}=dfrac{p-1}{left(p-1,dfrac{p+1}2right)}$



          Now, if integer $d(>0)$ divides both, $d$ must divide $-(p-1)+2cdotdfrac{p+1}2=2$



          As for odd prime $p,p-1$ is even



          $left(p-1,dfrac{p+1}2right)=2$ if $dfrac{p+1}2$ is even $=2k$(say) $iff p=4k-1equiv-1pmod4$



          $left(p-1,dfrac{p+1}2right)=1$ if $dfrac{p+1}2$ is odd $=2k+1$(say) $iff p=4k+1equiv1pmod4$






          share|cite|improve this answer









          $endgroup$



          $$-g=g(-1)equiv g^{1+(p-1)/2}equiv g^{(p+1)/2}$$



          We know, ord$_ma=d, $ord$_m(a^k)=dfrac d{(d,k)}$ (Proof @Page$#95$)



          ord$_p g^{(p+1)/2}=dfrac{p-1}{left(p-1,dfrac{p+1}2right)}$



          Now, if integer $d(>0)$ divides both, $d$ must divide $-(p-1)+2cdotdfrac{p+1}2=2$



          As for odd prime $p,p-1$ is even



          $left(p-1,dfrac{p+1}2right)=2$ if $dfrac{p+1}2$ is even $=2k$(say) $iff p=4k-1equiv-1pmod4$



          $left(p-1,dfrac{p+1}2right)=1$ if $dfrac{p+1}2$ is odd $=2k+1$(say) $iff p=4k+1equiv1pmod4$







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          answered Dec 6 '18 at 11:40









          lab bhattacharjeelab bhattacharjee

          225k15157275




          225k15157275












          • $begingroup$
            See also: math.stackexchange.com/questions/56028/…
            $endgroup$
            – lab bhattacharjee
            Dec 6 '18 at 11:44


















          • $begingroup$
            See also: math.stackexchange.com/questions/56028/…
            $endgroup$
            – lab bhattacharjee
            Dec 6 '18 at 11:44
















          $begingroup$
          See also: math.stackexchange.com/questions/56028/…
          $endgroup$
          – lab bhattacharjee
          Dec 6 '18 at 11:44




          $begingroup$
          See also: math.stackexchange.com/questions/56028/…
          $endgroup$
          – lab bhattacharjee
          Dec 6 '18 at 11:44


















          draft saved

          draft discarded




















































          Thanks for contributing an answer to Mathematics Stack Exchange!


          • Please be sure to answer the question. Provide details and share your research!

          But avoid



          • Asking for help, clarification, or responding to other answers.

          • Making statements based on opinion; back them up with references or personal experience.


          Use MathJax to format equations. MathJax reference.


          To learn more, see our tips on writing great answers.




          draft saved


          draft discarded














          StackExchange.ready(
          function () {
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1229270%2fassuming-g-is-a-primitive-root-modulo-a-prime-p-show-that-p-g-is-a-primit%23new-answer', 'question_page');
          }
          );

          Post as a guest















          Required, but never shown





















































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown

































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown







          Popular posts from this blog

          Bundesstraße 106

          Verónica Boquete

          Ida-Boy-Ed-Garten