| | |
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} \quad \quad {\Tiny \textrm{ notably, one or the other, or both}}$$ or equivalently, $$\pm y \equiv x^2\pmod{p} \quad \quad {\Tiny \textrm{ again, one or the other, or both}}$$ Thus, one or the other, or both of $y$ and $-y$ are squares $\pmod{p}$. Notice this leaves the door open for the square roots of $y$ to exist but not be $\pm y^{(p+1)/4}\pmod{p}$, leaving these two values to serve as square roots for $-y$ instead. Our claim says something different. It says if $y$ has square roots, then these are $\pm y^{(p+1)/4}\pmod{p}$, period. If only we could eliminate the case that both $y$ and $-y$ could be squares at the same time...
Let us try to argue that only one of these can be a square then!
Arguing indirectly, suppose not!
Suppose there exist integers $a$ and $b$ such that $\pmod{p}$, we have $$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& (-1)^2 b^2 b^{-2}\\ &\equiv& 1 \end{array}$$Thus, $y^{-1} = -(b^{-1})^2$, requiring
$$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}$).Having found the requisite contradiction, we know that both $y$ and $-y$ can't have a square root $\pmod{p}$, and the rest of the claim is immediate.