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

• Depending on where your investigation leads you, the answer to a question like this could be a finite list of prime numbers. Or it could be some kind of formula in $n$ that outputs all such primes sequentially. Or it could just be another way to describe the set of such primes that is somehow more direct, like "all primes that are 3 modulo 8" or something similar. Without knowing where this will go it is not clear that it will literally be possible to "find" all such primes and write them all down. Commented Nov 13, 2012 at 1:10
• The question just says "all primes". I don't think it'd be enough to say all primes p that are a quadratic residue of 5 lol Commented Nov 13, 2012 at 1:32
• But would it be enough to say "all primes that are $\pm1\mod{5}$? Commented Nov 13, 2012 at 1:38
• I can't see any other way it could be put lol. I'll just do this. Thank you!!! Commented Nov 13, 2012 at 1:48

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 Dirichlet's theorem that there are infinitely many primes in 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.

• @Chloe.H I'm not quite sure I follow that. It is important that $5-1$ is divisible by $4$. That makes $\left(\frac{5}{p}\right)\cdot\left(\frac{p}{5}\right)=1$ for sure. So $5$ is a quadratic residue mod $p$ exactly when $p$ is quadratic residue mod $5$, which happens exactly when $p$ is $1$ or $4$ mod $5$. (Aka $\pm1$ mod $5$.) Commented Nov 13, 2012 at 1:36
• @Chloe.H Oh yes. Lots of things about primes work differently if it's $2$ we are talking about. For example, quadratic reciprocity ;) Commented Nov 13, 2012 at 4:19