Let $a$ and $p$ be integers such that $p$ is prime, and $a$ is a square modulo $p$. When $p\equiv3\pmod4$, show that $a^{(p+1)/4}\pmod p$ is a square root of $a$. Why does this technique not work when $p\equiv1\pmod4$?
This is a question that appeared on a past exam paper for Cryptography at Undergraduate level. I think it might have something to do with the Legendre Symbol: $(\frac{-1}{p}) =\begin{cases} 1 & \mbox{ if }p \equiv 1\mod{4} \\ -1 & \mbox{ if }p \equiv 3\mod{4}. \end{cases}$
But I cannot seem to make the connection here. I have also thought about the use of Euler's criterion $a^{(p-1)/2} \equiv (\frac{a}{p}) \equiv 1 \pmod p.$ But that does not mean $a^{(p-1)/4}$ is a square root of $a$.
Could anyone hint me please on the direction I should take? Thanks in advance!