1
$\begingroup$

Assume that the integer $r$ is a primitive root of the prime $p$, where $p \equiv 1 \pmod{8}$. Show that the solutions of the quadratic congruence $x^2 \equiv 2\pmod{p}$ are given by $x \equiv \pm (r^{7(p-1)/8}+r^{(p-1)/8}) \pmod{p}$


Here is my attempt so far

$$r \text{ is a primitive root } \implies \exists k: 2\equiv r^k \pmod{p}$$ I am not sure why the question is assuming the given quadratic congruence always has a solution. But if it has a solution, from Euler's criterian we have $$2^{(p-1)/2}\equiv 1\pmod{p}$$

I feel stuck at this point.. Any help is appreciated thanks!

$\endgroup$
1
$\begingroup$

Let $b=r^{(p-1)/8}$. Then $a=r^{7(p-1)/8}+r^{(p-1)/8}=b^7+b$ and so $a^2=b^{14}+2b^8+b^2$.

We want to prove that $a^2=2$.

Clearly, $b^8=1$. It remains to prove that $b^{14}+b^2=0$.

Now, $b^{14}+b^2=b^{6}+b^2=b^2(b^4+1)$.

But $b^4+1=0$ because $0=b^8-1=(b^4+1)(b^4-1)$, and $b^4-1\ne0$.

Thus, $x=\pm a$ are two solutions of $x^2=2$. That equation cannot have more than two solutions, since $\mathbb Z/p$ is a field. Hence, we have found them all.

$\endgroup$

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.