  ## Finding Square Roots

Claim:

When $p \equiv 3\pmod{4}$ is prime, and $y$ is an integer that has square roots $\pmod{p}$, these square roots are $x \equiv \pm y^{(p+1)/4}\pmod{p}$. If $y$ has no square roots $\pmod{p}$, then these values for $x$ are square roots of $-y$ instead.

Proof:

If $y \equiv 0\pmod{p}$, the above conclusions are trivial.

If $y \not\equiv 0\pmod{p}$, then by Fermat's Little Theorem, we know $$y^{p-1} \equiv 1\pmod{p}$$ but then, $$x^4 \equiv y^{p+1} \equiv y^2 y^{p-1} \equiv y^2\pmod{p}$$ So $$\begin{array}{rcl} y^2 - x^4&\equiv& 0\pmod{p}\\ (y+x^2)(y-x^2) &\equiv& 0\pmod{p} \end{array}$$ As such, $$y \equiv \pm x^2\pmod{p}$$ or equivalently, $$\pm y \equiv x^2\pmod{p}$$ Therefore, at least one of $y$ and $-y$ is a square $\pmod{p}$. Suppose both are squares -- that is to say, $$y \equiv a^2 \quad \textrm{ and } \quad -y \equiv b^2$$ Recalling that $y \not\equiv 0$, so $gcd(y,p) = 1$, we know that $y^{-1}\pmod{p}$ exists. Further, if $y \not\equiv 0$, then $-y = b^2 \not\equiv 0$ as well, and so $b \not\equiv 0$. Consequently $b^{-1}\pmod{p}$ exists too.

Consider $-(b^{-1})^2$. We can easily show this is the multiplicative inverse of $y$, as

$$\begin{array}{rcl} y \cdot -(b^{-1})^2 &\equiv& (-b^2) \cdot -(b^{-1})^2\\ &\equiv& (-b^2) \cdot -(b^{-1})^2\\ &\equiv& b \cdot b \cdot b^{-1} \cdot b^{-1}\\ &\equiv& b \cdot 1 \cdot b^{-1}\\ &\equiv& b \cdot b^{-1}\\ &\equiv& 1 \end{array}$$

Thus, starting with $y=a^2$, and noting $y^{-1} = -(b^{-1})^2$, consider multiplying one by the other to find

$$y \cdot y^{-1} = a^2 \cdot -(b^{-1})^2$$

Collapsing the left and pulling the factor of $-1$ on the right to the left side, we have

$$-1 \equiv a^2 b^{-2} = (ab^{-1})^2$$ So $-1$ is a square $\pmod{p}$. However, this is impossible when working with a prime $p \equiv 3 \pmod{4}$. To see this, suppose $p = 4k+3$, and some value $z$ when squared is $-1$ modulo $p$. Then, $$\begin{array}{rcl} z^2 &\equiv& -1 \pmod{p}\\ (z^2)^{(p-1)/2} &\equiv& (-1)^{(p-1)/2}\\ z^{p-1} &\equiv& (-1)^{((4k+3)-1)/2}\\ z^{p-1} &\equiv& (-1)^{2k+1}\\ z^{p-1} &\equiv& -1 \end{array}$$ This of course contradicts what we know by Fermat's Little Theorem to be true (i.e., $z^{p-1} \equiv 1\pmod{p}$).

Therefore, exactly one of $y$ and $-y$ has a square root $\pmod{p}$, and the rest of the claim is immediate.