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!
Best Answer
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$.