What primes $p$ give solutions to $x^{2} equiv 7 ($mod $ p)$












-1












$begingroup$


I'm trying to understand how to solve this using the Legendre symbol but am having a hard time figuring out exactly what to do.



There are many different cases to consider but I do not know how to approach this problem.






number-theory quadratic-residues







share|cite|improve this question











$endgroup$












  • $begingroup$
    What are you stuck on? Do you know what the Legendre symbol actually is?
    $endgroup$
    – anomaly
    Nov 28 '18 at 0:58












  • $begingroup$
    It tells us whether we have a quadratic or non quadratic residue. I'm just not too familiar with computing it
    $endgroup$
    – Wallace
    Nov 28 '18 at 1:01
















-1












$begingroup$


I'm trying to understand how to solve this using the Legendre symbol but am having a hard time figuring out exactly what to do.



There are many different cases to consider but I do not know how to approach this problem.






number-theory quadratic-residues







share|cite|improve this question











$endgroup$












  • $begingroup$
    What are you stuck on? Do you know what the Legendre symbol actually is?
    $endgroup$
    – anomaly
    Nov 28 '18 at 0:58












  • $begingroup$
    It tells us whether we have a quadratic or non quadratic residue. I'm just not too familiar with computing it
    $endgroup$
    – Wallace
    Nov 28 '18 at 1:01














-1












-1








-1





$begingroup$


I'm trying to understand how to solve this using the Legendre symbol but am having a hard time figuring out exactly what to do.



There are many different cases to consider but I do not know how to approach this problem.






number-theory quadratic-residues







share|cite|improve this question











$endgroup$




I'm trying to understand how to solve this using the Legendre symbol but am having a hard time figuring out exactly what to do.



There are many different cases to consider but I do not know how to approach this problem.






number-theory quadratic-residues




number-theory quadratic-residues






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Nov 28 '18 at 1:08









Henning Makholm

239k17304541




239k17304541










asked Nov 28 '18 at 0:38









WallaceWallace

1297




1297












  • $begingroup$
    What are you stuck on? Do you know what the Legendre symbol actually is?
    $endgroup$
    – anomaly
    Nov 28 '18 at 0:58












  • $begingroup$
    It tells us whether we have a quadratic or non quadratic residue. I'm just not too familiar with computing it
    $endgroup$
    – Wallace
    Nov 28 '18 at 1:01


















  • $begingroup$
    What are you stuck on? Do you know what the Legendre symbol actually is?
    $endgroup$
    – anomaly
    Nov 28 '18 at 0:58












  • $begingroup$
    It tells us whether we have a quadratic or non quadratic residue. I'm just not too familiar with computing it
    $endgroup$
    – Wallace
    Nov 28 '18 at 1:01
















$begingroup$
What are you stuck on? Do you know what the Legendre symbol actually is?
$endgroup$
– anomaly
Nov 28 '18 at 0:58






$begingroup$
What are you stuck on? Do you know what the Legendre symbol actually is?
$endgroup$
– anomaly
Nov 28 '18 at 0:58














$begingroup$
It tells us whether we have a quadratic or non quadratic residue. I'm just not too familiar with computing it
$endgroup$
– Wallace
Nov 28 '18 at 1:01




$begingroup$
It tells us whether we have a quadratic or non quadratic residue. I'm just not too familiar with computing it
$endgroup$
– Wallace
Nov 28 '18 at 1:01










3 Answers
3






active

oldest

votes


















2












$begingroup$

Another hint:



An odd prime is congruent to $1$ or $3mod 4$. Also, the non-zero squares modulo $7$ are $;1,,2$ and $4$. So




  • If $pequiv 1mod 4$, $(-1)^{tfrac{p-1}2}=1$, and $p$ has to be a square modulo $7$, i.e. $pequiv 1,2,4$.

  • If $pequiv 3mod 4$, $p$ has to be a non-square modulo $7$, i.e. $pequiv3,5,6$


Now use the Chinese remainder theorem:
$$mathbf Z/4mathbf Ztimes mathbf Z/7mathbf Zsimeqmathbf Z/28mathbf Z$$
to find the images of the pairs ${(1,1),,(1,2),,(1,4),,(3,3),,(3,5),,(3,6)}$ modulo $28$.






share|cite|improve this answer











$endgroup$





















    2












    $begingroup$

    Hint: If $p$ is an odd prime not equal to $7$ ($p=2$ works, $p=7$ does not), we have by quadratic reciprocity that



    $$left(frac{p}{7}right)left(frac{7}{p}right)=(-1)^{frac{6(p-1)}{4}}=(-1)^{frac{p-1}{2}},$$



    so we need



    $$left(frac{p}{7}right)=(-1)^{frac{p-1}{2}}.$$



    Now look at each residue for $pbmod 7$ and determine what residue $pbmod 4$ must be.






    share|cite|improve this answer









    $endgroup$





















      0












      $begingroup$

      If either $p$ or $-p$ has an integer expression as $u^2 - 7 v^2,$ it follows that there is a solution to $$ u^2 equiv 7 v^2 pmod p ; . ; $$
      Which, you know, means something.



           2    29    37    53   109   113   137   149   193   197
      
   233   277   281   317   337   373   389   401   421   449
      
   457   541   557   569   613   617   641   653   673   701
      
   709   757   809   821   877   953   977  1009  1033  1061
      

      
     3     7    19    31    47    59    83   103   131   139
      
   167   199   223   227   251   271   283   307   311   367
      
   383   419   439   467   479   503   523   563   587   607
      
   619   643   647   691   719   727   787   811   839   859
      
   887   971   983  1039  1063  1091  1123  1151  1223  1231





      share|cite|improve this answer









      $endgroup$













        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%2f3016533%2fwhat-primes-p-give-solutions-to-x2-equiv-7-mod-p%23new-answer', 'question_page');
        }
        );

        Post as a guest















        Required, but never shown

























        3 Answers
        3






        active

        oldest

        votes








        3 Answers
        3






        active

        oldest

        votes









        active

        oldest

        votes






        active

        oldest

        votes









        2












        $begingroup$

        Another hint:



        An odd prime is congruent to $1$ or $3mod 4$. Also, the non-zero squares modulo $7$ are $;1,,2$ and $4$. So




        • If $pequiv 1mod 4$, $(-1)^{tfrac{p-1}2}=1$, and $p$ has to be a square modulo $7$, i.e. $pequiv 1,2,4$.

        • If $pequiv 3mod 4$, $p$ has to be a non-square modulo $7$, i.e. $pequiv3,5,6$


        Now use the Chinese remainder theorem:
        $$mathbf Z/4mathbf Ztimes mathbf Z/7mathbf Zsimeqmathbf Z/28mathbf Z$$
        to find the images of the pairs ${(1,1),,(1,2),,(1,4),,(3,3),,(3,5),,(3,6)}$ modulo $28$.






        share|cite|improve this answer











        $endgroup$


















          2












          $begingroup$

          Another hint:



          An odd prime is congruent to $1$ or $3mod 4$. Also, the non-zero squares modulo $7$ are $;1,,2$ and $4$. So




          • If $pequiv 1mod 4$, $(-1)^{tfrac{p-1}2}=1$, and $p$ has to be a square modulo $7$, i.e. $pequiv 1,2,4$.

          • If $pequiv 3mod 4$, $p$ has to be a non-square modulo $7$, i.e. $pequiv3,5,6$


          Now use the Chinese remainder theorem:
          $$mathbf Z/4mathbf Ztimes mathbf Z/7mathbf Zsimeqmathbf Z/28mathbf Z$$
          to find the images of the pairs ${(1,1),,(1,2),,(1,4),,(3,3),,(3,5),,(3,6)}$ modulo $28$.






          share|cite|improve this answer











          $endgroup$
















            2












            2








            2





            $begingroup$

            Another hint:



            An odd prime is congruent to $1$ or $3mod 4$. Also, the non-zero squares modulo $7$ are $;1,,2$ and $4$. So




            • If $pequiv 1mod 4$, $(-1)^{tfrac{p-1}2}=1$, and $p$ has to be a square modulo $7$, i.e. $pequiv 1,2,4$.

            • If $pequiv 3mod 4$, $p$ has to be a non-square modulo $7$, i.e. $pequiv3,5,6$


            Now use the Chinese remainder theorem:
            $$mathbf Z/4mathbf Ztimes mathbf Z/7mathbf Zsimeqmathbf Z/28mathbf Z$$
            to find the images of the pairs ${(1,1),,(1,2),,(1,4),,(3,3),,(3,5),,(3,6)}$ modulo $28$.






            share|cite|improve this answer











            $endgroup$



            Another hint:



            An odd prime is congruent to $1$ or $3mod 4$. Also, the non-zero squares modulo $7$ are $;1,,2$ and $4$. So




            • If $pequiv 1mod 4$, $(-1)^{tfrac{p-1}2}=1$, and $p$ has to be a square modulo $7$, i.e. $pequiv 1,2,4$.

            • If $pequiv 3mod 4$, $p$ has to be a non-square modulo $7$, i.e. $pequiv3,5,6$


            Now use the Chinese remainder theorem:
            $$mathbf Z/4mathbf Ztimes mathbf Z/7mathbf Zsimeqmathbf Z/28mathbf Z$$
            to find the images of the pairs ${(1,1),,(1,2),,(1,4),,(3,3),,(3,5),,(3,6)}$ modulo $28$.







            share|cite|improve this answer














            share|cite|improve this answer



            share|cite|improve this answer








            edited Nov 28 '18 at 9:25

























            answered Nov 28 '18 at 1:06









            BernardBernard

            119k740113




            119k740113























                2












                $begingroup$

                Hint: If $p$ is an odd prime not equal to $7$ ($p=2$ works, $p=7$ does not), we have by quadratic reciprocity that



                $$left(frac{p}{7}right)left(frac{7}{p}right)=(-1)^{frac{6(p-1)}{4}}=(-1)^{frac{p-1}{2}},$$



                so we need



                $$left(frac{p}{7}right)=(-1)^{frac{p-1}{2}}.$$



                Now look at each residue for $pbmod 7$ and determine what residue $pbmod 4$ must be.






                share|cite|improve this answer









                $endgroup$


















                  2












                  $begingroup$

                  Hint: If $p$ is an odd prime not equal to $7$ ($p=2$ works, $p=7$ does not), we have by quadratic reciprocity that



                  $$left(frac{p}{7}right)left(frac{7}{p}right)=(-1)^{frac{6(p-1)}{4}}=(-1)^{frac{p-1}{2}},$$



                  so we need



                  $$left(frac{p}{7}right)=(-1)^{frac{p-1}{2}}.$$



                  Now look at each residue for $pbmod 7$ and determine what residue $pbmod 4$ must be.






                  share|cite|improve this answer









                  $endgroup$
















                    2












                    2








                    2





                    $begingroup$

                    Hint: If $p$ is an odd prime not equal to $7$ ($p=2$ works, $p=7$ does not), we have by quadratic reciprocity that



                    $$left(frac{p}{7}right)left(frac{7}{p}right)=(-1)^{frac{6(p-1)}{4}}=(-1)^{frac{p-1}{2}},$$



                    so we need



                    $$left(frac{p}{7}right)=(-1)^{frac{p-1}{2}}.$$



                    Now look at each residue for $pbmod 7$ and determine what residue $pbmod 4$ must be.






                    share|cite|improve this answer









                    $endgroup$



                    Hint: If $p$ is an odd prime not equal to $7$ ($p=2$ works, $p=7$ does not), we have by quadratic reciprocity that



                    $$left(frac{p}{7}right)left(frac{7}{p}right)=(-1)^{frac{6(p-1)}{4}}=(-1)^{frac{p-1}{2}},$$



                    so we need



                    $$left(frac{p}{7}right)=(-1)^{frac{p-1}{2}}.$$



                    Now look at each residue for $pbmod 7$ and determine what residue $pbmod 4$ must be.







                    share|cite|improve this answer












                    share|cite|improve this answer



                    share|cite|improve this answer










                    answered Nov 28 '18 at 0:51









                    Carl SchildkrautCarl Schildkraut

                    11.3k11441




                    11.3k11441























                        0












                        $begingroup$

                        If either $p$ or $-p$ has an integer expression as $u^2 - 7 v^2,$ it follows that there is a solution to $$ u^2 equiv 7 v^2 pmod p ; . ; $$
                        Which, you know, means something.



                             2    29    37    53   109   113   137   149   193   197
                        
   233   277   281   317   337   373   389   401   421   449
                        
   457   541   557   569   613   617   641   653   673   701
                        
   709   757   809   821   877   953   977  1009  1033  1061
                        

                        
     3     7    19    31    47    59    83   103   131   139
                        
   167   199   223   227   251   271   283   307   311   367
                        
   383   419   439   467   479   503   523   563   587   607
                        
   619   643   647   691   719   727   787   811   839   859
                        
   887   971   983  1039  1063  1091  1123  1151  1223  1231





                        share|cite|improve this answer









                        $endgroup$


















                          0












                          $begingroup$

                          If either $p$ or $-p$ has an integer expression as $u^2 - 7 v^2,$ it follows that there is a solution to $$ u^2 equiv 7 v^2 pmod p ; . ; $$
                          Which, you know, means something.



                               2    29    37    53   109   113   137   149   193   197
                          
   233   277   281   317   337   373   389   401   421   449
                          
   457   541   557   569   613   617   641   653   673   701
                          
   709   757   809   821   877   953   977  1009  1033  1061
                          

                          
     3     7    19    31    47    59    83   103   131   139
                          
   167   199   223   227   251   271   283   307   311   367
                          
   383   419   439   467   479   503   523   563   587   607
                          
   619   643   647   691   719   727   787   811   839   859
                          
   887   971   983  1039  1063  1091  1123  1151  1223  1231





                          share|cite|improve this answer









                          $endgroup$
















                            0












                            0








                            0





                            $begingroup$

                            If either $p$ or $-p$ has an integer expression as $u^2 - 7 v^2,$ it follows that there is a solution to $$ u^2 equiv 7 v^2 pmod p ; . ; $$
                            Which, you know, means something.



                                 2    29    37    53   109   113   137   149   193   197
                            
   233   277   281   317   337   373   389   401   421   449
                            
   457   541   557   569   613   617   641   653   673   701
                            
   709   757   809   821   877   953   977  1009  1033  1061
                            

                            
     3     7    19    31    47    59    83   103   131   139
                            
   167   199   223   227   251   271   283   307   311   367
                            
   383   419   439   467   479   503   523   563   587   607
                            
   619   643   647   691   719   727   787   811   839   859
                            
   887   971   983  1039  1063  1091  1123  1151  1223  1231





                            share|cite|improve this answer









                            $endgroup$



                            If either $p$ or $-p$ has an integer expression as $u^2 - 7 v^2,$ it follows that there is a solution to $$ u^2 equiv 7 v^2 pmod p ; . ; $$
                            Which, you know, means something.



                                 2    29    37    53   109   113   137   149   193   197
                            
   233   277   281   317   337   373   389   401   421   449
                            
   457   541   557   569   613   617   641   653   673   701
                            
   709   757   809   821   877   953   977  1009  1033  1061
                            

                            
     3     7    19    31    47    59    83   103   131   139
                            
   167   199   223   227   251   271   283   307   311   367
                            
   383   419   439   467   479   503   523   563   587   607
                            
   619   643   647   691   719   727   787   811   839   859
                            
   887   971   983  1039  1063  1091  1123  1151  1223  1231






                            share|cite|improve this answer












                            share|cite|improve this answer



                            share|cite|improve this answer










                            answered Nov 28 '18 at 2:28









                            Will JagyWill Jagy

                            103k5101200




                            103k5101200






























                                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%2f3016533%2fwhat-primes-p-give-solutions-to-x2-equiv-7-mod-p%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

                                mysqli_query(): Empty query in /home/lucindabrummitt/public_html/blog/wp-includes/wp-db.php on line 1924

                                Image
                                0 I just uploaded a new plugin to my wordpress site and I got this warning: mysqli_query(): Empty query in /home/lucindabrummitt/public_html/blog/wp-includes/wp-db.php on line 1924 Usually if I have a problem, I can find answers on google but this one seems pretty particular and I'm not finding any info on it except for this forum. I'm not terribly techie but if someone can tell me how to read this and how to change it I can follow directions pretty well. Thanks All! PS If I don't have the proper tags here could someone add the appropriate tags? php mysql wordpress share | improve this question asked Nov 16 '18 at 20:41 ...
                                Read more

                                How to change which sound is reproduced for terminal bell?

                                Image
                                3 Recently upgrade to 18.10 from 18.04, and using the terminal is becoming annoying: the new alert sound is a drip ( /usr/share/sounds/gnome/default/alerts/drip.ogg ), and the previous one is still located at ( /usr/share/sounds/ubuntu/stereo/bell.ogg ). My issue is that at the gnome-terminal, when autocompleting or pressing left BOTH sounds are reproduced, at the same time. I want to just have ubuntu/stereo/bell.ogg active, not both . At the moment I have been only able to reduce the volume of the alerts (but still both are played), or turn the alerts down (but I dislike both "solutions"). gnome-terminal 18.10 teminal-bell share | improve this question ...
                                Read more

                                Can I use Tabulator js library in my java Spring + Thymeleaf project?

                                Image
                                0 I want to add Tabulator js to my java project. I added tabulator.min.js, tabulator.min.css to resources folder. After that added to my html page these dependencies as recommending in readme.md. <link rel="stylesheet" th:href="@{/css/tabulator.min.css}"> <script type="text/javascript" th:src="@{/js/tabulator.min.js}"></script> Now my tables view all elements, that I have in the html page, but not correct. In the documentation of Tabulator is example how to create header and table, var table = new Tabulator("#example-table", { columns:[ {title:"Name", field:"name", sorter:"string", width:200, editor:true}, {title:"Age", field:"age", sorter:"...
                                Read more