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 Answer 1

2
$\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$
1
  • $\begingroup$ Clearer: $\ \large b^4\equiv -1\,\Rightarrow\, b^{2}\equiv -b^{-2}\,\Rightarrow\, (b^7+b)^2\equiv (b^{-1}+b)^2\equiv 2\ \ $ $\endgroup$ Commented May 25, 2020 at 6:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .