$n^2 \equiv (-5) \mod p$

Question

I need to determine all primes p for which -5 is a quadratic residue modulo p. The original question is

Find the odd primes which divide integers of the form $n^2+5$ ?

My try:

what I obtain is ... $$n^2 \equiv (-5) \mod p$$ I know how to solve $n^2 \equiv 5 \mod p$ what is the difference if it is replaced by -5 . Does it mean... every prime of the form $$p=\pm 1 , \pm3 \mod 10 ??$$

Answer 1

We have the Legendre symbol $$\left(\frac{-5}p\right)=\left(\frac5p\right)\left(\frac{-1}p\right)=+1$$

There are two main cases:

• If both Legendre symbols are $+1$, then (as already shown) either $p=5$ (the exceptional case) or $p\equiv\pm1\bmod5$. $\left(\frac{-1}p\right)=+1$ precisely when $p\equiv1\bmod4$. Combining these two congruences yields $p\equiv1,9\bmod20$.
• If both Legendre symbols are $-1$, solving each symbol yields $p\equiv\pm2\bmod5$ and $p\equiv3\bmod4$, or $p\equiv3,7\bmod20$.

Therefore, the odd primes that are factors of $n^2+5$ are $5$ and those congruent to $1,3,7,9\bmod20$.

Answer 2

The possible prime factors upto $5$ are $2,3,5$ which can be found out by inspection.

For primes $p>5$ , we have to distinguish between two cases :

$(1)$ $p=4k+1$. In this case, $-1$ is a quadratic residue and hence also $5$. So, the possible forms are $20k+1$ and $20k+9$

$(2)$ $p=4k+3$. In this case, $-1$ is not a quadratic residue, so neither is $5$. So, the possible forms are $20k+3$ and $20k+7$