# Solutions of $x^2 \equiv \pm 2 \ (\text{mod} \ p)$ and primitive root modulo $p.$

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.

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

• 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? – Alexy Vincenzo Nov 8 '18 at 16:52
• 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. – Richard Martin Nov 8 '18 at 17:01