When $p=3 \pmod 4$, show that $a^{(p+1)/4} \pmod p$ is a square root of $a$

Question

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!

Answer 1

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$.

Answer 2

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$

Answer 3

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.