If $p = 8n+1$ is a prime and $r$ is a primitive root modulo $p,$ then the solutions of $x^2 \equiv \pm 2 \ (\text{mod} \ p)$ are given by $x \equiv \pm(r^{7n} \pm r^n) \ (\text{mod} \ p).$

Again, I have shown that $x \equiv (r^{7n} + r^n) \ (\text{mod} \ p)$ is solution to $x^2 \equiv 2 \ (\text{mod} \ p)$ and $x \equiv (-r^{7n} + r^n) \ (\text{mod} \ p)$ is solution to $x^2 \equiv -2 \ (\text{mod} \ p).$

Could anyone advise me on how to show they are all the possible solutions? Thank you.

  • $\begingroup$ There are at most two square roots of a residue $\pmod p$. If you have found two, you must have found them all. $\endgroup$ – lulu Nov 8 '18 at 16:40
  • $\begingroup$ But how do I know they must be in the form? $\endgroup$ – Alexy Vincenzo Nov 8 '18 at 16:46
  • $\begingroup$ You say you have proven that those are solutions, since you found the right number of them you are done. $\endgroup$ – lulu Nov 8 '18 at 16:48

See #2990050 which deals with essentially the same question.

  • $\begingroup$ Noted. But how do I know the solutions must be in such form? $\endgroup$ – Alexy Vincenzo Nov 8 '18 at 16:47
  • $\begingroup$ Well you've shown that these do the job and there cannot be more than two of them. $\endgroup$ – Richard Martin Nov 8 '18 at 16:48
  • $\begingroup$ I quoted this problem from textbook. The question requires us to show that $x \equiv \pm(r^{7n} \pm r^n) \ (\text{mod} \ p)$ are the solutions. How does one come up with the explicit form of the solutions? What is the intuition or thought process in coming up with the 'solution' before proving it is indeed the solution? $\endgroup$ – Alexy Vincenzo Nov 8 '18 at 16:52
  • $\begingroup$ Hmmm. How about this: $(w^n + w^{-n})^2 = w^{2n} + w^{-2n} + 2$. Now arrange for $w^{2n} = - w^{-2n}$. It all boils down to roots of unity. $\endgroup$ – Richard Martin Nov 8 '18 at 17:01
  • $\begingroup$ I think it provides an answer to his question about the intuition of the thought process in coming up with the solution. $\endgroup$ – Richard Martin Nov 9 '18 at 10:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.