When $p=3 \pmod 4$, show that $a^{(p+1)/4} \pmod p$ is a square root of $a$ 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!
 A: When you mentioned Euler's Criterion, you were nearly finished. Let $a$ be a quadratic residue of $p$.  Then 
$$a^{(p-1)/2}\equiv 1\pmod{p}.\tag{1}$$
Multiplying by $a$ we get
$$a^{(p+1)/2}\equiv a\pmod{p}.\tag{2}$$
If $p$ is of the form $4k+3$, then $\frac{p+1}{4}$ is an integer, and from (2) we obtain
$$\left(a^{(p+1)/4}  \right)^2\equiv a\pmod{p}.$$
Remark: The method does not work for primes of the form $4k+1$ for the simple reason that  $\frac{p+1}{4}$ is then not an integer. There is a modification of the idea for primes of the form $8k+5$, which uses facts about the quadratic character of $2$.
A: If $a$ is divisible by $p$, the assertion is trivial.  Otherwise, we want to know whether $a^{\frac{p+1}{4}}$ squared is congruent to $a$ modulo $p$.  Just work backwards: $$a^{\frac{p+1}{2}} \equiv a \pmod p $$ if and only if (multiplying both sides by $a^{-1}$): $$a^{\frac{p-1}{2}} \equiv 1 \pmod p$$ This last assertion is true because in your hypothesis you said there is some $x$ for which $a \equiv x^2$, whence (raising both sides to the $(p-1)/2$ power) $$a^{\frac{p-1}{2}} \equiv x^{p-1} \equiv 1 \pmod p$$ Since $a$ is not divisible by $p$, neither is $x$, so of course $x^{p-1} \equiv 1$.  We cannot even formulate your assertion when $p$ is not $3$ modulo $4$, since otherwise $(p+1)/4$ is not even an integer.  But besides being able to pose a well defined problem, I didn't use $p \equiv 3 \pmod 4$ anywhere, only that $p$ was odd.
A: Hint: if $p \equiv 3 \mod 4$, then $a^{\frac{p+1}{4}} = a^m, m \in \Bbb Z$
And if $p \equiv 1 \mod 4$ then $a^{\frac{p+1}{4}} = a^{\frac{1}{2}} a^m, m \in \Bbb Z$
