Find all primes such that $x^{2} = -1$ has no solution in $\mathbb{F}_p$

Question

Find all the prime numbers such that $x^{2} = -1$ doesn't have a solution in $\mathbb{F}_p = \mathbb{Z}/p \mathbb{Z}$.

I am not sure how to start this problem, but I have in intuition of the familie of prime numbers. My intuition is that $p = 3\mod 4$.

If anyone as suggestions to give me, I would appreciate it.

Answer 1

We want to show that $-1$ is a quadratic residue mod $p$ for odd prime $p$ if and only if $p \equiv 1 \bmod 4$. Thus (to answer your original problem) $-1$ is a quadratic nonresidue mod $p$ if and only if $p \equiv 3 \bmod 4$.

The simplest demonstration uses Euler's criterion for an odd prime $p$, which says for any $a$ not divisible by $p$, $a$ is a quadratic residue mod $p$ if and only if:

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

Now first let's apply this proposition to $a=-1$ to get our desired result, then sketch the proof of Euler's criterion.

When $p\equiv 1 \bmod 4$, then $\frac{p-1}{2}$ is an even integer. Of course this means raising $-1$ to the power $\frac{p-1}{2}$ will give $1$, and Euler's criterion tells us that $-1$ is a quadratic residue. On the other hand if $p \equiv 3 \bmod 4$, then $\frac{p-1}{2}$ is an odd integer. Thus in that case $-1$ would be a quadratic nonresidue.

[NB: The only other possibility for a prime is $p=2$, and then $-1$ is the same residue as $+1$. Hence for $p=2$ we have $-1$ is a quadratic residue.]

Sketch of proof of Euler's criterion:

Recall by Fermat's little theorem that $b^{p-1} \equiv 1 \bmod p$ provided $p$ is prime and does not divide $b$. Hence if $a$ were a quadratic residue mod $p$ (coprime to $p$), we could take $b^2 = a \bmod p$ and get:

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

To state the contrapositive, if applying Euler's criterion gave $a{\frac{p-1}{2}} \not\equiv 1 \bmod p$, then $a$ would be a quadratic nonresidue. Now to finish the proof, we do some root counting.

With $p$ an odd prime, the equation in Fermat's little theorem $a^{p-1} \equiv 1$ has exactly $p-1$ distinct roots. Since $p$ is odd, this polynomial can be factored:

$$ \left( a^{\frac{p-1}{2}} - 1\right) \left( a^{\frac{p-1}{2}} + 1\right) \equiv 0 \bmod p$$

Now Lagrange's theorem says that each of these factors has at most $(p-1)/2$ roots. But altogether there are exactly $p-1$ roots between them, so each factor must have exactly $(p-1)/2$ distinct roots.

Note that since $p$ is an odd prime, nonzero residue $x\not\equiv -x$. So squaring all the $p-1$ nonzero residues shows us there are exactly $(p-1)/2$ quadratic residues. From what we already argued, any quadratic residues must be roots of the first factor. It follows that the roots of the second factor are quadratic nonresidues and conversely. This completes the proof of Euler's criterion.

Answer 2

This problem is fairly easy once you know $F_p$ is a field with a cyclic group of units. Since $x^2=-1$ we know that $x$ must have order $4$. Thus $4|p-1$ by Lagrange. Thus $p-1=0$ mod (4) is necessary. It is also sufficient as units of $F_p$ are a cyclic group so if $4|p-1$ there is a cyclic subgroup of order $4$. Therefore, it has no solution $\iff$ $p-1\not=0$ mod (4)