Solving $x^2\equiv a\pmod{p}$ where $p\equiv5\pmod{8}$ and $a$ is a quadratic residue

Question

The exercise asks me to show that one of the values $x = a^{(p+3)/8}$ and $x = 2a \cdot (4a)^{(p-5)/8}$ is a solution to $x^2\equiv a\pmod{p}$, where $p\equiv5\pmod{8}$ is a prime and $a$ is a quadratic residue. My reasoning was that $a^{(p-1)/2} \equiv a^{(8k+5-1)/2} \equiv a^{4k+2} \equiv 1 \pmod{p}$ by Euler's criterion and therefore $a^{2k+1} \equiv \pm 1\pmod{p}$. Therefore $x = a^{(p+3)/8}$ has $x^2 = a^{2k+2} \equiv a \pmod{p}$ when $a^{2k+1} \equiv 1 \pmod{p}$. I am struggling to show that $x = 2a \cdot (4a)^{(p-5)/8}$ is a solution when $a^{2k+1} \equiv -1 \pmod{p}$.

Answer 1

Recall that $p \equiv 5 \mod 8$, and thus $p \not\equiv \pm 1 \mod 8$. Thus, the second supplement to the law of Quadratic Reciprocity shows that $2$ is a quadratic non-residue modulo $p$. In other words, the Legendre symbol $\left(\dfrac{2}{p}\right) = -1$. But Legendre's formula says that $\left(\dfrac{a}{p}\right) \equiv a^{\left(p-1\right)/2} \mod p$ for any integer $a$ coprime to $p$. Applying this to $a=2$, we obtain $\left(\dfrac{2}{p}\right) \equiv 2^{\left(p-1\right)/2} = 2^{4k+2} \mod p$ (since $\left(p-1\right)/2 = 4k+2$). Compared with $\left(\dfrac{2}{p}\right) = -1$, this becomes $2^{4k+2} \equiv -1 \mod p$.

Assume that $a^{2k+1} \equiv -1 \mod p$. Set $x = 2a \cdot \left(4a\right)^{\left(p-5\right)/8}$. Thus,

$x^2 = \left(2a \cdot \left(4a\right)^{\left(p-5\right)/8}\right)^2 = \left(2a \cdot \left(4a\right)^{k}\right)^2$ (since $\left(p-5\right)/8=k$)

$= 4a^2 \left(4a\right)^{2k} = a \left(4a\right)^{2k+1} = a \underbrace{4^{2k+1}}_{=2^{2\left(2k+1\right)} = 2^{4k+2} \equiv -1 \mod p} \underbrace{a^{2k+1}}_{\equiv -1 \mod p} \equiv a \left(-1\right)\left(-1\right) = a \mod p$,

qed.