7
$\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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – 2'5 9'2
    Commented Nov 13, 2012 at 1:10
  • $\begingroup$ 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 $\endgroup$
    – Chloe.H
    Commented Nov 13, 2012 at 1:32
  • $\begingroup$ But would it be enough to say "all primes that are $\pm1\mod{5}$? $\endgroup$
    – 2'5 9'2
    Commented Nov 13, 2012 at 1:38
  • $\begingroup$ I can't see any other way it could be put lol. I'll just do this. Thank you!!! $\endgroup$
    – Chloe.H
    Commented Nov 13, 2012 at 1:48

2 Answers 2

Reset to default
7
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Thank you!! The embarrassing part is I skimmed through that article a while ago. Guess I skipped over that important part! Thanks again $\endgroup$
    – Chloe.H
    Commented Nov 13, 2012 at 1:15
  • $\begingroup$ OK. So does the following make sense: since 5 is prime, the only quadratic residues of it are +/-1. Thus, if 5 is a quadric residue of p, then p is a quadratic residue of 5 which implies p is 1? $\endgroup$
    – Chloe.H
    Commented Nov 13, 2012 at 1:21
  • $\begingroup$ @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$.) $\endgroup$
    – 2'5 9'2
    Commented Nov 13, 2012 at 1:36
  • 1
    $\begingroup$ Right. But doesn't 5-1 divisable by 5 imply (5/p)(p/5) = 1 for p not equal to 2? because then 2-1 = 1 and (-1)^1 = -1 $\endgroup$
    – Chloe.H
    Commented Nov 13, 2012 at 1:48
  • $\begingroup$ @Chloe.H Oh yes. Lots of things about primes work differently if it's $2$ we are talking about. For example, quadratic reciprocity ;) $\endgroup$
    – 2'5 9'2
    Commented Nov 13, 2012 at 4:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .