Finding quadratic residues without Legendre symbols The Next CEO of Stack OverflowReduction of the question of quadratic residues mod $m$ to the primary decomposition of $m$.Quadratic Residues in $mathbbZ/3^n mathbbZ $Proof dealing with Quadratic ResiduesSolvability of quadratic congruenceLet $a$ be a quadratic residue modulo $p$. Prove that the number $bequiv a^fracp+14 mod p$ has the property that $b^2equiv a mod p$.$4n$ is a square modulo $d$ implies $n$ is a square modulo $d$Hypothesis on quadratic residues and cyclic generatorsQuadratic Residues ProofNo canonical non-quadratic residue for primes $equiv 1 bmod 8$?Understanding this proof regarding quadratic residues

Can you teleport closer to a creature you are Frightened of?

Is it ok to trim down a tube patch?

What day is it again?

Would a grinding machine be a simple and workable propulsion system for an interplanetary spacecraft?

Lucky Feat: How can "more than one creature spend a luck point to influence the outcome of a roll"?

Airplane gently rocking its wings during whole flight

Touchpad not working on Debian 9

Graph of the history of databases

Can this note be analyzed as a non-chord tone?

IC has pull-down resistors on SMBus lines?

Is French Guiana a (hard) EU border?

Is there a way to save my career from absolute disaster?

Which one is the true statement?

Scary film where a woman has vaginal teeth

How did Beeri the Hittite come up with naming his daughter Yehudit?

Do I need to write [sic] when including a quotation with a number less than 10 that isn't written out?

Can I board the first leg of the flight without having final country's visa?

Reshaping json / reparing json inside shell script (remove trailing comma)

Could a dragon use its wings to swim?

Does Germany produce more waste than the US?

Can I calculate next year's exemptions based on this year's refund/amount owed?

Is it okay to majorly distort historical facts while writing a fiction story?

It is correct to match light sources with the same color temperature?

Expectation in a stochastic differential equation



Finding quadratic residues without Legendre symbols



The Next CEO of Stack OverflowReduction of the question of quadratic residues mod $m$ to the primary decomposition of $m$.Quadratic Residues in $mathbbZ/3^n mathbbZ $Proof dealing with Quadratic ResiduesSolvability of quadratic congruenceLet $a$ be a quadratic residue modulo $p$. Prove that the number $bequiv a^fracp+14 mod p$ has the property that $b^2equiv a mod p$.$4n$ is a square modulo $d$ implies $n$ is a square modulo $d$Hypothesis on quadratic residues and cyclic generatorsQuadratic Residues ProofNo canonical non-quadratic residue for primes $equiv 1 bmod 8$?Understanding this proof regarding quadratic residues










7












$begingroup$


I ran into two very similar problems concerning quadratic residues, and I'm having a bit of trouble working through them. These problems are supposed to rely exclusively on the theory of cyclic groups, without use of Legendre symbols. I'm posting both in one question since I roughly managed to solve the first one and it's meant to show my thought process towards solving the second.




Let $p$ be a prime congruent to $1$ modulo $3$. Show that there exists
an $a in mathbbZ$ such that $a^2 + a + 1 equiv 0 textrm mod p$ and
conclude that $-3$ is a square modulo $p$.




To solve this one, I let $p = 3k + 1$, and take $g in (mathbbZ_p, times)$ to be a generator from which follows that $g^3k - 1 = (g^k - 1)(g^2k + g^k + 1) equiv 0 textrm mod p$. Since $g$ is a generator, $g^k ne 1$. To conclude $-3$ is a square, I (somewhat randomly) noticed that



beginalign*
(g^k - g^-k)^2 &= g^2k - 2 + g^-2k \
&= g^2k + g^k + 1 - 3 \
&equiv -3 textrm mod p
endalign*



I was wondering, is there any significance to the element $g^k - g^-k$ as a root for $-3$? Is there any way to intuitively know immediately that's the square you're looking for? I remember seeing similarly defined elements before, and I pretty much just plugged it in hoping for the best, without really knowing what I was doing. The next problem has me completely stumped.




Let $p$ be a prime congruent to $1$ modulo $5$. Show that there exists
an $a in mathbbZ$ such that $(a + a⁴)² + (a + a⁴) - 1 equiv 0 textrm mod p$ and conclude that $5$ is a square modulo $p$.




I sort of have this sense that I'm gonna need an element of order $10$, i.e. $g^frac5k2$ where $g$ is yet again a generator, however I can't seem to get anywhere with this. If I let $x = a + a^4$, then I can tell I'm basically looking for an element $x$ which has the next element $x + 1$ as its inverse, but that doesn't really help me forward.










share|cite|improve this question









$endgroup$
















    7












    $begingroup$


    I ran into two very similar problems concerning quadratic residues, and I'm having a bit of trouble working through them. These problems are supposed to rely exclusively on the theory of cyclic groups, without use of Legendre symbols. I'm posting both in one question since I roughly managed to solve the first one and it's meant to show my thought process towards solving the second.




    Let $p$ be a prime congruent to $1$ modulo $3$. Show that there exists
    an $a in mathbbZ$ such that $a^2 + a + 1 equiv 0 textrm mod p$ and
    conclude that $-3$ is a square modulo $p$.




    To solve this one, I let $p = 3k + 1$, and take $g in (mathbbZ_p, times)$ to be a generator from which follows that $g^3k - 1 = (g^k - 1)(g^2k + g^k + 1) equiv 0 textrm mod p$. Since $g$ is a generator, $g^k ne 1$. To conclude $-3$ is a square, I (somewhat randomly) noticed that



    beginalign*
    (g^k - g^-k)^2 &= g^2k - 2 + g^-2k \
    &= g^2k + g^k + 1 - 3 \
    &equiv -3 textrm mod p
    endalign*



    I was wondering, is there any significance to the element $g^k - g^-k$ as a root for $-3$? Is there any way to intuitively know immediately that's the square you're looking for? I remember seeing similarly defined elements before, and I pretty much just plugged it in hoping for the best, without really knowing what I was doing. The next problem has me completely stumped.




    Let $p$ be a prime congruent to $1$ modulo $5$. Show that there exists
    an $a in mathbbZ$ such that $(a + a⁴)² + (a + a⁴) - 1 equiv 0 textrm mod p$ and conclude that $5$ is a square modulo $p$.




    I sort of have this sense that I'm gonna need an element of order $10$, i.e. $g^frac5k2$ where $g$ is yet again a generator, however I can't seem to get anywhere with this. If I let $x = a + a^4$, then I can tell I'm basically looking for an element $x$ which has the next element $x + 1$ as its inverse, but that doesn't really help me forward.










    share|cite|improve this question









    $endgroup$














      7












      7








      7





      $begingroup$


      I ran into two very similar problems concerning quadratic residues, and I'm having a bit of trouble working through them. These problems are supposed to rely exclusively on the theory of cyclic groups, without use of Legendre symbols. I'm posting both in one question since I roughly managed to solve the first one and it's meant to show my thought process towards solving the second.




      Let $p$ be a prime congruent to $1$ modulo $3$. Show that there exists
      an $a in mathbbZ$ such that $a^2 + a + 1 equiv 0 textrm mod p$ and
      conclude that $-3$ is a square modulo $p$.




      To solve this one, I let $p = 3k + 1$, and take $g in (mathbbZ_p, times)$ to be a generator from which follows that $g^3k - 1 = (g^k - 1)(g^2k + g^k + 1) equiv 0 textrm mod p$. Since $g$ is a generator, $g^k ne 1$. To conclude $-3$ is a square, I (somewhat randomly) noticed that



      beginalign*
      (g^k - g^-k)^2 &= g^2k - 2 + g^-2k \
      &= g^2k + g^k + 1 - 3 \
      &equiv -3 textrm mod p
      endalign*



      I was wondering, is there any significance to the element $g^k - g^-k$ as a root for $-3$? Is there any way to intuitively know immediately that's the square you're looking for? I remember seeing similarly defined elements before, and I pretty much just plugged it in hoping for the best, without really knowing what I was doing. The next problem has me completely stumped.




      Let $p$ be a prime congruent to $1$ modulo $5$. Show that there exists
      an $a in mathbbZ$ such that $(a + a⁴)² + (a + a⁴) - 1 equiv 0 textrm mod p$ and conclude that $5$ is a square modulo $p$.




      I sort of have this sense that I'm gonna need an element of order $10$, i.e. $g^frac5k2$ where $g$ is yet again a generator, however I can't seem to get anywhere with this. If I let $x = a + a^4$, then I can tell I'm basically looking for an element $x$ which has the next element $x + 1$ as its inverse, but that doesn't really help me forward.










      share|cite|improve this question









      $endgroup$




      I ran into two very similar problems concerning quadratic residues, and I'm having a bit of trouble working through them. These problems are supposed to rely exclusively on the theory of cyclic groups, without use of Legendre symbols. I'm posting both in one question since I roughly managed to solve the first one and it's meant to show my thought process towards solving the second.




      Let $p$ be a prime congruent to $1$ modulo $3$. Show that there exists
      an $a in mathbbZ$ such that $a^2 + a + 1 equiv 0 textrm mod p$ and
      conclude that $-3$ is a square modulo $p$.




      To solve this one, I let $p = 3k + 1$, and take $g in (mathbbZ_p, times)$ to be a generator from which follows that $g^3k - 1 = (g^k - 1)(g^2k + g^k + 1) equiv 0 textrm mod p$. Since $g$ is a generator, $g^k ne 1$. To conclude $-3$ is a square, I (somewhat randomly) noticed that



      beginalign*
      (g^k - g^-k)^2 &= g^2k - 2 + g^-2k \
      &= g^2k + g^k + 1 - 3 \
      &equiv -3 textrm mod p
      endalign*



      I was wondering, is there any significance to the element $g^k - g^-k$ as a root for $-3$? Is there any way to intuitively know immediately that's the square you're looking for? I remember seeing similarly defined elements before, and I pretty much just plugged it in hoping for the best, without really knowing what I was doing. The next problem has me completely stumped.




      Let $p$ be a prime congruent to $1$ modulo $5$. Show that there exists
      an $a in mathbbZ$ such that $(a + a⁴)² + (a + a⁴) - 1 equiv 0 textrm mod p$ and conclude that $5$ is a square modulo $p$.




      I sort of have this sense that I'm gonna need an element of order $10$, i.e. $g^frac5k2$ where $g$ is yet again a generator, however I can't seem to get anywhere with this. If I let $x = a + a^4$, then I can tell I'm basically looking for an element $x$ which has the next element $x + 1$ as its inverse, but that doesn't really help me forward.







      number-theory prime-numbers modular-arithmetic cyclic-groups quadratic-residues






      share|cite|improve this question













      share|cite|improve this question











      share|cite|improve this question




      share|cite|improve this question










      asked 2 days ago









      ZenoZeno

      846




      846




















          2 Answers
          2






          active

          oldest

          votes


















          2












          $begingroup$

          Hint: If $a^5 = 1$ then $a^4 = a^-1$ and $(a+a^4)^2 + (a+a^4) - 1 = a^-2(a^4 + a^3 + a^2 + a + 1)$.



          Also if $x^2 + x - 1 = 0$ in $mathbb Z_p$, then $4(x^2 + x - 1) = (2x+1)^2 - 5 = 0$.






          share|cite|improve this answer











          $endgroup$












          • $begingroup$
            Right, ofcourse. The sum of all roots of unity equals zero. That was a crucial bit I was missing. I'm assuming you forgot an exponent on your $2$ in your second line but I understand what you're doing, thank you.
            $endgroup$
            – Zeno
            2 days ago






          • 1




            $begingroup$
            Fixed, thank you. The 2 you saw in the second line should be in the parenthesis.
            $endgroup$
            – Hw Chu
            2 days ago










          • $begingroup$
            Also is it possible the $a^-2$ at the end is kind of arbitrary? Unless I'm mistaken using the distributive property $a(a^4 + a^3 + a^2 + a + 1) = a^5 + a^4 + a^3 + a^2 + a = a^4 + a^3 + a^2 + a + 1$ which would mean you can fill in just about any power of a instead of just $a^-2$.
            $endgroup$
            – Zeno
            yesterday











          • $begingroup$
            Well that is true. By the same reason as in your post, if $a neq 1$ and $a^5 = 1$, then $a^4 + a^3 + a^2 + a + 1 = 0$ so changing $a^-2$ to anything else yields a zero after all. That $a^-2$ term emerges from the expansion of $$(a+a^4)^2 + (a+a^4) - 1 = (a + a^-1)^2 + (a + a^-1) - 1 = cdots$$
            $endgroup$
            – Hw Chu
            yesterday


















          2












          $begingroup$

          A substantial part of your question seems to be “how do I intuitively arrive at an expression which yields the desired square root?”. I want to address this first.



          In both cases the question is structured as “show there exists a solution to this quadratic, hence $d$ is a square modulo $p$”. In the first question the quadratic is $x^2+x+1$, and in the second question it’s $x^2+x-1$. Notice that in each case the desired square root is exactly the discriminant $b^2 - 4ac$ from the quadratic formula.



          Intuitively, the idea is that if a ring contains solutions to the quadratic then the square root in the quadratic formula “should” work in that ring. (This isn’t universally true: when a cubic polynomial has all real roots, the cubic formula still involves taking square roots of negative numbers.). The way to expose this explicitly is just to complete the square:



          $$x^2 + x + 1 = 0, \
          4x^2 + 4x + 4 = 0, \
          4x^2 + 4x + 1 = -3, \
          (2x+1)^2 = -3.$$



          As for how to guess at the element which makes it work, in both cases we know that $mathbb Z_p$ contains a primitive $r$th root of unity for $r=3$ and $r=5$ respectively. In some sense that’s about all the specialized knowledge we possess. I think the author is hoping/expecting the reader to first try plugging in that root of unity into $a$, since there’s no simpler value to choose from, and the questions are designed to make this work on that first try.



          For the second question it may have resulted in a rather intimidating-looking expression hiding inside the quadratic, but presumably the intent was for the first question to go very smoothly, giving the reader the hope that the exact same strategy will work for the second.






          share|cite|improve this answer









          $endgroup$








          • 1




            $begingroup$
            Crystal clear, thank you. It would seem I can't approve both answers simultaneously even though they both kinda contributed to me fully understanding the problem
            $endgroup$
            – Zeno
            2 days ago











          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%2f3167222%2ffinding-quadratic-residues-without-legendre-symbols%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









          2












          $begingroup$

          Hint: If $a^5 = 1$ then $a^4 = a^-1$ and $(a+a^4)^2 + (a+a^4) - 1 = a^-2(a^4 + a^3 + a^2 + a + 1)$.



          Also if $x^2 + x - 1 = 0$ in $mathbb Z_p$, then $4(x^2 + x - 1) = (2x+1)^2 - 5 = 0$.






          share|cite|improve this answer











          $endgroup$












          • $begingroup$
            Right, ofcourse. The sum of all roots of unity equals zero. That was a crucial bit I was missing. I'm assuming you forgot an exponent on your $2$ in your second line but I understand what you're doing, thank you.
            $endgroup$
            – Zeno
            2 days ago






          • 1




            $begingroup$
            Fixed, thank you. The 2 you saw in the second line should be in the parenthesis.
            $endgroup$
            – Hw Chu
            2 days ago










          • $begingroup$
            Also is it possible the $a^-2$ at the end is kind of arbitrary? Unless I'm mistaken using the distributive property $a(a^4 + a^3 + a^2 + a + 1) = a^5 + a^4 + a^3 + a^2 + a = a^4 + a^3 + a^2 + a + 1$ which would mean you can fill in just about any power of a instead of just $a^-2$.
            $endgroup$
            – Zeno
            yesterday











          • $begingroup$
            Well that is true. By the same reason as in your post, if $a neq 1$ and $a^5 = 1$, then $a^4 + a^3 + a^2 + a + 1 = 0$ so changing $a^-2$ to anything else yields a zero after all. That $a^-2$ term emerges from the expansion of $$(a+a^4)^2 + (a+a^4) - 1 = (a + a^-1)^2 + (a + a^-1) - 1 = cdots$$
            $endgroup$
            – Hw Chu
            yesterday















          2












          $begingroup$

          Hint: If $a^5 = 1$ then $a^4 = a^-1$ and $(a+a^4)^2 + (a+a^4) - 1 = a^-2(a^4 + a^3 + a^2 + a + 1)$.



          Also if $x^2 + x - 1 = 0$ in $mathbb Z_p$, then $4(x^2 + x - 1) = (2x+1)^2 - 5 = 0$.






          share|cite|improve this answer











          $endgroup$












          • $begingroup$
            Right, ofcourse. The sum of all roots of unity equals zero. That was a crucial bit I was missing. I'm assuming you forgot an exponent on your $2$ in your second line but I understand what you're doing, thank you.
            $endgroup$
            – Zeno
            2 days ago






          • 1




            $begingroup$
            Fixed, thank you. The 2 you saw in the second line should be in the parenthesis.
            $endgroup$
            – Hw Chu
            2 days ago










          • $begingroup$
            Also is it possible the $a^-2$ at the end is kind of arbitrary? Unless I'm mistaken using the distributive property $a(a^4 + a^3 + a^2 + a + 1) = a^5 + a^4 + a^3 + a^2 + a = a^4 + a^3 + a^2 + a + 1$ which would mean you can fill in just about any power of a instead of just $a^-2$.
            $endgroup$
            – Zeno
            yesterday











          • $begingroup$
            Well that is true. By the same reason as in your post, if $a neq 1$ and $a^5 = 1$, then $a^4 + a^3 + a^2 + a + 1 = 0$ so changing $a^-2$ to anything else yields a zero after all. That $a^-2$ term emerges from the expansion of $$(a+a^4)^2 + (a+a^4) - 1 = (a + a^-1)^2 + (a + a^-1) - 1 = cdots$$
            $endgroup$
            – Hw Chu
            yesterday













          2












          2








          2





          $begingroup$

          Hint: If $a^5 = 1$ then $a^4 = a^-1$ and $(a+a^4)^2 + (a+a^4) - 1 = a^-2(a^4 + a^3 + a^2 + a + 1)$.



          Also if $x^2 + x - 1 = 0$ in $mathbb Z_p$, then $4(x^2 + x - 1) = (2x+1)^2 - 5 = 0$.






          share|cite|improve this answer











          $endgroup$



          Hint: If $a^5 = 1$ then $a^4 = a^-1$ and $(a+a^4)^2 + (a+a^4) - 1 = a^-2(a^4 + a^3 + a^2 + a + 1)$.



          Also if $x^2 + x - 1 = 0$ in $mathbb Z_p$, then $4(x^2 + x - 1) = (2x+1)^2 - 5 = 0$.







          share|cite|improve this answer














          share|cite|improve this answer



          share|cite|improve this answer








          edited 2 days ago

























          answered 2 days ago









          Hw ChuHw Chu

          3,337519




          3,337519











          • $begingroup$
            Right, ofcourse. The sum of all roots of unity equals zero. That was a crucial bit I was missing. I'm assuming you forgot an exponent on your $2$ in your second line but I understand what you're doing, thank you.
            $endgroup$
            – Zeno
            2 days ago






          • 1




            $begingroup$
            Fixed, thank you. The 2 you saw in the second line should be in the parenthesis.
            $endgroup$
            – Hw Chu
            2 days ago










          • $begingroup$
            Also is it possible the $a^-2$ at the end is kind of arbitrary? Unless I'm mistaken using the distributive property $a(a^4 + a^3 + a^2 + a + 1) = a^5 + a^4 + a^3 + a^2 + a = a^4 + a^3 + a^2 + a + 1$ which would mean you can fill in just about any power of a instead of just $a^-2$.
            $endgroup$
            – Zeno
            yesterday











          • $begingroup$
            Well that is true. By the same reason as in your post, if $a neq 1$ and $a^5 = 1$, then $a^4 + a^3 + a^2 + a + 1 = 0$ so changing $a^-2$ to anything else yields a zero after all. That $a^-2$ term emerges from the expansion of $$(a+a^4)^2 + (a+a^4) - 1 = (a + a^-1)^2 + (a + a^-1) - 1 = cdots$$
            $endgroup$
            – Hw Chu
            yesterday
















          • $begingroup$
            Right, ofcourse. The sum of all roots of unity equals zero. That was a crucial bit I was missing. I'm assuming you forgot an exponent on your $2$ in your second line but I understand what you're doing, thank you.
            $endgroup$
            – Zeno
            2 days ago






          • 1




            $begingroup$
            Fixed, thank you. The 2 you saw in the second line should be in the parenthesis.
            $endgroup$
            – Hw Chu
            2 days ago










          • $begingroup$
            Also is it possible the $a^-2$ at the end is kind of arbitrary? Unless I'm mistaken using the distributive property $a(a^4 + a^3 + a^2 + a + 1) = a^5 + a^4 + a^3 + a^2 + a = a^4 + a^3 + a^2 + a + 1$ which would mean you can fill in just about any power of a instead of just $a^-2$.
            $endgroup$
            – Zeno
            yesterday











          • $begingroup$
            Well that is true. By the same reason as in your post, if $a neq 1$ and $a^5 = 1$, then $a^4 + a^3 + a^2 + a + 1 = 0$ so changing $a^-2$ to anything else yields a zero after all. That $a^-2$ term emerges from the expansion of $$(a+a^4)^2 + (a+a^4) - 1 = (a + a^-1)^2 + (a + a^-1) - 1 = cdots$$
            $endgroup$
            – Hw Chu
            yesterday















          $begingroup$
          Right, ofcourse. The sum of all roots of unity equals zero. That was a crucial bit I was missing. I'm assuming you forgot an exponent on your $2$ in your second line but I understand what you're doing, thank you.
          $endgroup$
          – Zeno
          2 days ago




          $begingroup$
          Right, ofcourse. The sum of all roots of unity equals zero. That was a crucial bit I was missing. I'm assuming you forgot an exponent on your $2$ in your second line but I understand what you're doing, thank you.
          $endgroup$
          – Zeno
          2 days ago




          1




          1




          $begingroup$
          Fixed, thank you. The 2 you saw in the second line should be in the parenthesis.
          $endgroup$
          – Hw Chu
          2 days ago




          $begingroup$
          Fixed, thank you. The 2 you saw in the second line should be in the parenthesis.
          $endgroup$
          – Hw Chu
          2 days ago












          $begingroup$
          Also is it possible the $a^-2$ at the end is kind of arbitrary? Unless I'm mistaken using the distributive property $a(a^4 + a^3 + a^2 + a + 1) = a^5 + a^4 + a^3 + a^2 + a = a^4 + a^3 + a^2 + a + 1$ which would mean you can fill in just about any power of a instead of just $a^-2$.
          $endgroup$
          – Zeno
          yesterday





          $begingroup$
          Also is it possible the $a^-2$ at the end is kind of arbitrary? Unless I'm mistaken using the distributive property $a(a^4 + a^3 + a^2 + a + 1) = a^5 + a^4 + a^3 + a^2 + a = a^4 + a^3 + a^2 + a + 1$ which would mean you can fill in just about any power of a instead of just $a^-2$.
          $endgroup$
          – Zeno
          yesterday













          $begingroup$
          Well that is true. By the same reason as in your post, if $a neq 1$ and $a^5 = 1$, then $a^4 + a^3 + a^2 + a + 1 = 0$ so changing $a^-2$ to anything else yields a zero after all. That $a^-2$ term emerges from the expansion of $$(a+a^4)^2 + (a+a^4) - 1 = (a + a^-1)^2 + (a + a^-1) - 1 = cdots$$
          $endgroup$
          – Hw Chu
          yesterday




          $begingroup$
          Well that is true. By the same reason as in your post, if $a neq 1$ and $a^5 = 1$, then $a^4 + a^3 + a^2 + a + 1 = 0$ so changing $a^-2$ to anything else yields a zero after all. That $a^-2$ term emerges from the expansion of $$(a+a^4)^2 + (a+a^4) - 1 = (a + a^-1)^2 + (a + a^-1) - 1 = cdots$$
          $endgroup$
          – Hw Chu
          yesterday











          2












          $begingroup$

          A substantial part of your question seems to be “how do I intuitively arrive at an expression which yields the desired square root?”. I want to address this first.



          In both cases the question is structured as “show there exists a solution to this quadratic, hence $d$ is a square modulo $p$”. In the first question the quadratic is $x^2+x+1$, and in the second question it’s $x^2+x-1$. Notice that in each case the desired square root is exactly the discriminant $b^2 - 4ac$ from the quadratic formula.



          Intuitively, the idea is that if a ring contains solutions to the quadratic then the square root in the quadratic formula “should” work in that ring. (This isn’t universally true: when a cubic polynomial has all real roots, the cubic formula still involves taking square roots of negative numbers.). The way to expose this explicitly is just to complete the square:



          $$x^2 + x + 1 = 0, \
          4x^2 + 4x + 4 = 0, \
          4x^2 + 4x + 1 = -3, \
          (2x+1)^2 = -3.$$



          As for how to guess at the element which makes it work, in both cases we know that $mathbb Z_p$ contains a primitive $r$th root of unity for $r=3$ and $r=5$ respectively. In some sense that’s about all the specialized knowledge we possess. I think the author is hoping/expecting the reader to first try plugging in that root of unity into $a$, since there’s no simpler value to choose from, and the questions are designed to make this work on that first try.



          For the second question it may have resulted in a rather intimidating-looking expression hiding inside the quadratic, but presumably the intent was for the first question to go very smoothly, giving the reader the hope that the exact same strategy will work for the second.






          share|cite|improve this answer









          $endgroup$








          • 1




            $begingroup$
            Crystal clear, thank you. It would seem I can't approve both answers simultaneously even though they both kinda contributed to me fully understanding the problem
            $endgroup$
            – Zeno
            2 days ago















          2












          $begingroup$

          A substantial part of your question seems to be “how do I intuitively arrive at an expression which yields the desired square root?”. I want to address this first.



          In both cases the question is structured as “show there exists a solution to this quadratic, hence $d$ is a square modulo $p$”. In the first question the quadratic is $x^2+x+1$, and in the second question it’s $x^2+x-1$. Notice that in each case the desired square root is exactly the discriminant $b^2 - 4ac$ from the quadratic formula.



          Intuitively, the idea is that if a ring contains solutions to the quadratic then the square root in the quadratic formula “should” work in that ring. (This isn’t universally true: when a cubic polynomial has all real roots, the cubic formula still involves taking square roots of negative numbers.). The way to expose this explicitly is just to complete the square:



          $$x^2 + x + 1 = 0, \
          4x^2 + 4x + 4 = 0, \
          4x^2 + 4x + 1 = -3, \
          (2x+1)^2 = -3.$$



          As for how to guess at the element which makes it work, in both cases we know that $mathbb Z_p$ contains a primitive $r$th root of unity for $r=3$ and $r=5$ respectively. In some sense that’s about all the specialized knowledge we possess. I think the author is hoping/expecting the reader to first try plugging in that root of unity into $a$, since there’s no simpler value to choose from, and the questions are designed to make this work on that first try.



          For the second question it may have resulted in a rather intimidating-looking expression hiding inside the quadratic, but presumably the intent was for the first question to go very smoothly, giving the reader the hope that the exact same strategy will work for the second.






          share|cite|improve this answer









          $endgroup$








          • 1




            $begingroup$
            Crystal clear, thank you. It would seem I can't approve both answers simultaneously even though they both kinda contributed to me fully understanding the problem
            $endgroup$
            – Zeno
            2 days ago













          2












          2








          2





          $begingroup$

          A substantial part of your question seems to be “how do I intuitively arrive at an expression which yields the desired square root?”. I want to address this first.



          In both cases the question is structured as “show there exists a solution to this quadratic, hence $d$ is a square modulo $p$”. In the first question the quadratic is $x^2+x+1$, and in the second question it’s $x^2+x-1$. Notice that in each case the desired square root is exactly the discriminant $b^2 - 4ac$ from the quadratic formula.



          Intuitively, the idea is that if a ring contains solutions to the quadratic then the square root in the quadratic formula “should” work in that ring. (This isn’t universally true: when a cubic polynomial has all real roots, the cubic formula still involves taking square roots of negative numbers.). The way to expose this explicitly is just to complete the square:



          $$x^2 + x + 1 = 0, \
          4x^2 + 4x + 4 = 0, \
          4x^2 + 4x + 1 = -3, \
          (2x+1)^2 = -3.$$



          As for how to guess at the element which makes it work, in both cases we know that $mathbb Z_p$ contains a primitive $r$th root of unity for $r=3$ and $r=5$ respectively. In some sense that’s about all the specialized knowledge we possess. I think the author is hoping/expecting the reader to first try plugging in that root of unity into $a$, since there’s no simpler value to choose from, and the questions are designed to make this work on that first try.



          For the second question it may have resulted in a rather intimidating-looking expression hiding inside the quadratic, but presumably the intent was for the first question to go very smoothly, giving the reader the hope that the exact same strategy will work for the second.






          share|cite|improve this answer









          $endgroup$



          A substantial part of your question seems to be “how do I intuitively arrive at an expression which yields the desired square root?”. I want to address this first.



          In both cases the question is structured as “show there exists a solution to this quadratic, hence $d$ is a square modulo $p$”. In the first question the quadratic is $x^2+x+1$, and in the second question it’s $x^2+x-1$. Notice that in each case the desired square root is exactly the discriminant $b^2 - 4ac$ from the quadratic formula.



          Intuitively, the idea is that if a ring contains solutions to the quadratic then the square root in the quadratic formula “should” work in that ring. (This isn’t universally true: when a cubic polynomial has all real roots, the cubic formula still involves taking square roots of negative numbers.). The way to expose this explicitly is just to complete the square:



          $$x^2 + x + 1 = 0, \
          4x^2 + 4x + 4 = 0, \
          4x^2 + 4x + 1 = -3, \
          (2x+1)^2 = -3.$$



          As for how to guess at the element which makes it work, in both cases we know that $mathbb Z_p$ contains a primitive $r$th root of unity for $r=3$ and $r=5$ respectively. In some sense that’s about all the specialized knowledge we possess. I think the author is hoping/expecting the reader to first try plugging in that root of unity into $a$, since there’s no simpler value to choose from, and the questions are designed to make this work on that first try.



          For the second question it may have resulted in a rather intimidating-looking expression hiding inside the quadratic, but presumably the intent was for the first question to go very smoothly, giving the reader the hope that the exact same strategy will work for the second.







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          answered 2 days ago









          Erick WongErick Wong

          20.4k22666




          20.4k22666







          • 1




            $begingroup$
            Crystal clear, thank you. It would seem I can't approve both answers simultaneously even though they both kinda contributed to me fully understanding the problem
            $endgroup$
            – Zeno
            2 days ago












          • 1




            $begingroup$
            Crystal clear, thank you. It would seem I can't approve both answers simultaneously even though they both kinda contributed to me fully understanding the problem
            $endgroup$
            – Zeno
            2 days ago







          1




          1




          $begingroup$
          Crystal clear, thank you. It would seem I can't approve both answers simultaneously even though they both kinda contributed to me fully understanding the problem
          $endgroup$
          – Zeno
          2 days ago




          $begingroup$
          Crystal clear, thank you. It would seem I can't approve both answers simultaneously even though they both kinda contributed to me fully understanding the problem
          $endgroup$
          – Zeno
          2 days ago

















          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%2f3167222%2ffinding-quadratic-residues-without-legendre-symbols%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

          រឿង រ៉ូមេអូ និង ហ្ស៊ុយលីយេ សង្ខេបរឿង តួអង្គ បញ្ជីណែនាំ

          Crop image to path created in TikZ? Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)Crop an inserted image?TikZ pictures does not appear in posterImage behind and beyond crop marks?Tikz picture as large as possible on A4 PageTransparency vs image compression dilemmaHow to crop background from image automatically?Image does not cropTikzexternal capturing crop marks when externalizing pgfplots?How to include image path that contains a dollar signCrop image with left size given

          Romeo and Juliet ContentsCharactersSynopsisSourcesDate and textThemes and motifsCriticism and interpretationLegacyScene by sceneSee alsoNotes and referencesSourcesExternal linksNavigation menu"Consumer Price Index (estimate) 1800–"10.2307/28710160037-3222287101610.1093/res/II.5.31910.2307/45967845967810.2307/2869925286992510.1525/jams.1982.35.3.03a00050"Dada Masilo: South African dancer who breaks the rules"10.1093/res/os-XV.57.1610.2307/28680942868094"Sweet Sorrow: Mann-Korman's Romeo and Juliet Closes Sept. 5 at MN's Ordway"the original10.2307/45957745957710.1017/CCOL0521570476.009"Ram Leela box office collections hit massive Rs 100 crore, pulverises prediction"Archived"Broadway Revival of Romeo and Juliet, Starring Orlando Bloom and Condola Rashad, Will Close Dec. 8"Archived10.1075/jhp.7.1.04hon"Wherefore art thou, Romeo? To make us laugh at Navy Pier"the original10.1093/gmo/9781561592630.article.O006772"Ram-leela Review Roundup: Critics Hail Film as Best Adaptation of Romeo and Juliet"Archived10.2307/31946310047-77293194631"Romeo and Juliet get Twitter treatment""Juliet's Nurse by Lois Leveen""Romeo and Juliet: Orlando Bloom's Broadway Debut Released in Theaters for Valentine's Day"Archived"Romeo and Juliet Has No Balcony"10.1093/gmo/9781561592630.article.O00778110.2307/2867423286742310.1076/enst.82.2.115.959510.1080/00138380601042675"A plague o' both your houses: error in GCSE exam paper forces apology""Juliet of the Five O'Clock Shadow, and Other Wonders"10.2307/33912430027-4321339124310.2307/28487440038-7134284874410.2307/29123140149-661129123144728341M"Weekender Guide: Shakespeare on The Drive""balcony"UK public library membership"romeo"UK public library membership10.1017/CCOL9780521844291"Post-Zionist Critique on Israel and the Palestinians Part III: Popular Culture"10.2307/25379071533-86140377-919X2537907"Capulets and Montagues: UK exam board admit mixing names up in Romeo and Juliet paper"Istoria Novellamente Ritrovata di Due Nobili Amanti2027/mdp.390150822329610820-750X"GCSE exam error: Board accidentally rewrites Shakespeare"10.2307/29176390149-66112917639"Exam board apologises after error in English GCSE paper which confused characters in Shakespeare's Romeo and Juliet""From Mariotto and Ganozza to Romeo and Guilietta: Metamorphoses of a Renaissance Tale"10.2307/37323537323510.2307/2867455286745510.2307/28678912867891"10 Questions for Taylor Swift"10.2307/28680922868092"Haymarket Theatre""The Zeffirelli Way: Revealing Talk by Florentine Director""Michael Smuin: 1938-2007 / Prolific dance director had showy career"The Life and Art of Edwin BoothRomeo and JulietRomeo and JulietRomeo and JulietRomeo and JulietEasy Read Romeo and JulietRomeo and Julieteeecb12003684p(data)4099369-3n8211610759dbe00d-a9e2-41a3-b2c1-977dd692899302814385X313670221313670221