Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 1 down vote favorite

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. Ie. I need to need to find numbers p where x^2 is congruent to 5 mod p. I'm ok doing this for single values of p. But how do I find all primes for which this holds? Thanks

share|improve this question
   
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. – alex.jordan Nov 13 '12 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 – Chloe.H Nov 13 '12 at 1:32
But would it be enough to say "all primes that are $\pm1\mod{5}$? – alex.jordan Nov 13 '12 at 1:38
I can't see any other way it could be put lol. I'll just do this. Thank you!!! – Chloe.H Nov 13 '12 at 1:48

1 Answer

up vote 1 down vote accepted

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

share|improve this answer
Thank you!! The embarrassing part is I skimmed through that article a while ago. Guess I skipped over that important part! Thanks again – Chloe.H Nov 13 '12 at 1:15
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? – Chloe.H Nov 13 '12 at 1:21
@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$.) – alex.jordan Nov 13 '12 at 1:36
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 – Chloe.H Nov 13 '12 at 1:48
@Chloe.H Oh yes. Lots of things about primes work differently if it's $2$ we are talking about. For example, quadratic reciprocity ;) – alex.jordan Nov 13 '12 at 4:19

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.