Determine all primes $p$ for which $5$ is a quadratic residue modulo $p$

I need to determine all primes $p$ for which $5$ is a quadratic residue modulo p.

I think I'll need to use quadratic recprocity laws to do this, i.e., I need to need to find numbers $p$ where $x^2$ is congruent to $5 \bmod p$. I'm ok doing this for single values of $p$. But how do I find all primes for which this holds?

Thanks.

Solution 1:

It is easy to verify that $\left(\dfrac{5}{p} \right) = \left(\dfrac{p}{5}\right)$. We know that $\left(\dfrac{p}{5} \right) =1$ when $p$ is quadratic residue modulo $5$. So $p = 1\pmod 5$ or $4 \pmod 5$. Therefore, for every prime $p$ in the arithmetic progression $1+5j, 5$ is residue. Similarly, for every prime $p$ in the progression $4+5j, 5$ is residue.

We know from Diritchlet theorem that there are infinitely many primes any arithmetic progression $a+bj$, for fixed co-prime pair $(a,b)$. So just search for first few primes in the progressions $1+5j, 4+5j$. (You can see that first few primes with this property are $11, 41, 29$, ...etc).

To my knowledge, there is no algorithm that performs better than brute force technique for finding primes in the given arithmetic progression.