# 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.

#### Solutions Collecting From Web of "Determine all primes $p$ for which $5$ is a quadratic residue modulo $p$"

Here is a Wikipedia article. Scroll up for review about quadratic reciprocity.

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.