4
$\begingroup$

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.

  • 0
    I can't see any other way it could be put lol. I'll just do this. Thank you!!!2012-11-13

2 Answers 2

2

Here is a Wikipedia article. Scroll up for review about quadratic reciprocity. http://en.wikipedia.org/wiki/Quadratic_reciprocity#.C2.B15

  • 0
    @Chloe.H Oh yes. Lots of things about primes work differently if it's $2$ we are talking about. For example, quadratic reciprocity ;)2012-11-13
5

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.