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











up vote
-1
down vote

favorite












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
























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












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















up vote
-1
down vote

favorite












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
























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












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













up vote
-1
down vote

favorite









up vote
-1
down vote

favorite











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















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 at 1:08









Henning Makholm

236k16300534




236k16300534










asked Nov 28 at 0:38









Wallace

1226




1226












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












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


















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












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
















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






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














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




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










3 Answers
3






active

oldest

votes

















up vote
2
down vote



accepted










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






























    up vote
    2
    down vote













    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




























      up vote
      0
      down vote













      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





















        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',
        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








        up vote
        2
        down vote



        accepted










        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



























          up vote
          2
          down vote



          accepted










          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

























            up vote
            2
            down vote



            accepted







            up vote
            2
            down vote



            accepted






            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














            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 at 9:25

























            answered Nov 28 at 1:06









            Bernard

            117k637109




            117k637109






















                up vote
                2
                down vote













                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

























                  up vote
                  2
                  down vote













                  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























                    up vote
                    2
                    down vote










                    up vote
                    2
                    down vote









                    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












                    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 at 0:51









                    Carl Schildkraut

                    11k11439




                    11k11439






















                        up vote
                        0
                        down vote













                        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

























                          up vote
                          0
                          down vote













                          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























                            up vote
                            0
                            down vote










                            up vote
                            0
                            down vote









                            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












                            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 at 2:28









                            Will Jagy

                            101k598198




                            101k598198






























                                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.





                                Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


                                Please pay close attention to the following guidance:


                                • 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.


                                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

                                Berounka

                                Image
                                Berounka.mw-parser-output .entete.map{background-image:url("//upload.wikimedia.org/wikipedia/commons/7/7a/Picto_infobox_map.png")} Caractéristiques Longueur 139  km Bassin 8 861  km 2 Bassin collecteur Elbe Débit moyen ? Cours Source Confluence de la Mže et de la Radbuza · Localisation Pilsen · Altitude 305  m · Coordonnées 49° 45′ 13″ N, 13° 23′ 24″ E Confluence Vltava · Localisation Prague · Altitude 187  m · Coordonnées 49° 59′ 43″ N, 14° 24′ 04″ E Géographie Pays traversés   République tchèque modifier   La Berounka est une rivière de la République tchèque. Elle porte le nom de Mže depuis sa source en Allemagne près de la frontière jusqu'à sa confluence avec la Radbuza à Plzeň. Elle continue ensuite sous le nom de Berounka jusqu'à sa confluence avec la Vltava, près de Prague. La rivière est une destination prisée pour les amateurs de canoë, qui appréc...
                                Read more

                                Sphinx de Gizeh

                                Image
                                Pour les articles homonymes, voir Sphinx. Sphinx de Gizeh.mw-parser-output .entete.egypte-antique{background-image:url("//upload.wikimedia.org/wikipedia/commons/c/cc/Picto_infobox_ancient_Egypt.png")} Site d'Égypte antique Le visage du sphinx de Gizeh. Noms en arabe أبو الهول , Abou al-Hôl Localisation Région Basse-Égypte Coordonnées 29° 58′ 31″ nord, 31° 08′ 16″ est Géolocalisation sur la carte : Égypte Sphinx de Gizeh modifier   Le sphinx de Gizeh est la statue thérianthrope qui se dresse devant les grandes pyramides du plateau de Gizeh, en Basse-Égypte. Sculpture monumentale monolithique la plus grande du monde [ 1 ] avec 73,5 mètres de longueur, 14 mètres de largeur et 20,22 mètres de hauteur, elle représente un sphinx couchant. Réalisée vers -2500, elle serait attribuée à Djédefrê, l'un des pharaons de la IV e  dynastie, représentant son père le pharaon Khéops. Sommaire 1 Étymologie 2 Desc...
                                Read more

                                Different font size/position of beamer's navigation symbols template's content depending on regular/plain...

                                Image
                                3 Let's suppose I'd like to divert the navigation symbols template (e.g. in order replace them by the frame numbers, see this bug report ;) I would be facing troubles regarding the font size/position, depending on regular/plain frames, as shown by the following MCE. How could I get rid of these troubles? documentclass{beamer} usetheme{PaloAlto} setbeamertemplate{navigation symbols}{insertframenumber/inserttotalframenumber} begin{document} begin{frame} frametitle{A regular frame} end{frame} begin{frame}[plain] frametitle{A plain frame} end{frame} end{document} beamer header-footer share | improve this question asked Dec 10 '18 a...
                                Read more