Take the 2-minute tour ×
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.

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.

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

2 Answers 2

up vote 2 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

It is easy to verify that (5/p) = (p/5). We know that (p/5) = 1 when p is quadratic residue modulo 5. So p = 1(mod 5) or 4 (mod 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.

share|improve this answer

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.