How does one show that if $p = 4k + 3$ then $a^{k+1} \pmod p$ is a square root of $a$?

Question

I was trying to solve a question from CLRS where it asks to show that if a prime is of the form $p = 4k + 3$, then:

$$ a^{k+1} \pmod p$$

is a square root of $a$ when $a$ is a Quadratic Residue in $\mathbb{Z}^*_p$. I wasn't quite sure how to show that but I did notice the following:

If $a$ is a Quadratic Residue, then the Legendre Symbol is 1. Thus:

$$ a^{\frac{p-1}{2}} \equiv 1 \pmod p$$

If we substitute the form of $p = 4k + 3$ we get:

$$ a^{\frac{4k+3-1}{2}} \equiv a^{\frac{4k+2}{2}} \equiv a^{2k+1} \equiv 1 \pmod p$$

which in turn implies:

$$ a^{-2k} \equiv a \pmod p \implies (a^{-k})^2 \equiv a \pmod p $$

Therefore, one of the square roots of $a$ bust be $a^{-k}$. Therefore I am suspecting that somehow either $x = a^{-k}$ is the same as $a^{k+1}$ or $a^{k+1} = -x = -a^{-k}$. Not sure which one, but I will try to find out. I am so close!

Answer 1

From $a^{(p-1)/2}\equiv 1\pmod{p}$, by multiplying both sides by $a$ we get $$a^{(p+1)/2}\equiv a\pmod{p}.\tag{1}$$

But $\frac{p+1}{2}=2k+2$. Thus from (1) we have $(a^{k+1})^2\equiv a\pmod{p}$.

Answer 2

Since $a$ is a quadratic residue there is a $b$ so that $a\equiv b^2$.

Now notice $(a^{k+1})^2\equiv a^{2k+2} \equiv (b^2)^{2k+1}\equiv b^{4k+4} \equiv b^{4k+3}b\equiv b^p b$.

Fermat's little theorem tells us $b^p\equiv b$ and so $b^pb\equiv bb\equiv b^2 \equiv a$.

Which is what we wanted to prove (that $a^{k+1}$ is a square root of $a$ is the same thing as saying $(a^{k+1})^2\equiv a$).