let $p$ be prime a prime with $p = 5 \mod 8$. furthermore $r \in (\mathbb{Z}/p\mathbb{Z})^*$ of order 4 and let $a$ be a quadratic residue mod $p$. Prove the following:
a solution of $x^2 = a \mod p$ is given by $x = a^{\frac{p+3}{8}}$ or $x = r\cdot a^{\frac{p+3}{8}}$.
I tried the following:
Suppose $x = a^{\frac{p+3}{8}}$, then we see:
$x^2 = a^{\frac{p+3}{4}} = a^\frac{1}{2} \cdot a^\frac{p+1}{4} = (a \cdot (a^\frac{p+1}{2}))^{\frac{1}{2}} = (a \cdot (\frac{a}{p}))^\frac{1}{2}$. If I can prove that $(a \cdot (\frac{a}{p}))^\frac{1}{2} = a$, This would be a solution but i don't see why that should be true.
for the other solution I don't see what to do, any hints/tips/tricks would be much appreciated :)
Kees
Let $p=8k+5$. All congruences that follow are modulo $p$.
By Euler's Criterion we have $a^{4k+2}\equiv 1$. and therefore $a^{2k+1}\equiv \pm 1$.
If $a^{2k+1}\equiv 1$, then $a^{2k+2}\equiv a$, and $a\equiv (a^{k+1})^2$.
If $a^{2k+1}\equiv -1$, we have to work a little harder, that's where $r$ comes in. Since $r$ has order $4$, we have $r^2\equiv -1$, so $r^2a^{2k+1}\equiv 1$, so $r^2a^{2k+2}\equiv a$, and the result follows.
Remark: Suppose that we want to use this result to write an efficient program to solve the congruence $x^2\equiv a\pmod{p}$, where $p$ is of the form $8k+5$. How do we come up with a suitable $r$? Note that by a standard result $2$ is a quadratic non-residue of $p$, and therefore $2^{2k+1}$ has order $4$ modulo $p$.