Processing math: 0%
     

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} \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.