Assume $p \equiv 3 \pmod{4}$, and there exists $x$ such that $n \equiv x^2 \pmod{p}$, find one possible value of $x$ given $n$ , $p$

Question

From Assume $p \equiv3 \pmod 4$ and $n \equiv x^2\pmod p $. Given $n$ and > $p$, find one possible value of $x$., it appears that one possible value of x that fulfills Euler's criterion with the constraint for $p$ specified in the title is

$x \equiv n^{(p+1)/4}$.

But, I'm having trouble confirming this is a valid value of $x$.

Because with this value of $x$, I can square both sides to get

$x^2 \equiv n^{(p+1)/2}\pmod{p}$

Now combined with $n \equiv x^2 \pmod{p}$, this means

$n \equiv x^2 \equiv n^{(p+1)/2} \pmod{p}$.

Substituting this $n$ value back into Euler's criterion $n^{(p-1)/2} \equiv 1$, I get

$(n^{(p+1)/2)})^{(p-1)/2)} \equiv 1$

which gives

$n^{(p^2-1)/4} \equiv 1$

Now I'm stuck. $n^{(p^2-1)/4} \equiv 1$ doesn't seem to make sense, and doesn't verify the original $x$ is a valid value at all?

Answer 1

You know $n^{(p-1)/2}\equiv1\pmod p$.

Define $x=n^{(p+1)/4}$. Then $x^2=n^{(p+1)/2}=n^{(p-1)/2}n$. Therefore $x^2\equiv 1\times n\equiv n\pmod p$.

Answer 2

You don't substitute back into Euler's criterion, you factor a little and then simplify using Euler's criterion. $$ n^{(p+1)/2} = n \cdot n^{(p-1)/2} \cong n \cdot 1 \cong n \pmod{p} \text{.} $$