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.

So I have this problem;

Let p be an odd prime and let q be the smallest positive integer which is a quadratic non residue (mod p). Prove q is a prime.

So what I know is that, since q is the smallest positive integer which is a quadratic non residue (mod p) then Legendre symbol (q|p) = -1 = q^((p-1)/2) (mod p). But I'm not sure if this is the correct direction with what I am doing since I can't concluding anything (obviously) from this.

share|improve this question

2 Answers 2

up vote 4 down vote accepted

Hint: if $q$ is composite, it can be written as $ab$ where $a < q$ and $b < q$. Can $a$ and $b$ both be quadratic residues mod $p$?

share|improve this answer
    
So then Legendre Symbol (q|p) = (ab|p) = (a|p)*(b|p). In other words, one is -1 and the other is 1, since q is a quadratic non residue? How does this tell us q must be prime though? –  Jonathan Mckibbin Apr 21 at 2:01
    
Because if $a$ or $b$ is a nonresidue, $q$ wasn't the smallest nonresidue. –  Robert Israel Apr 21 at 2:06
    
Oh thank you! Slipped right passed me. –  Jonathan Mckibbin Apr 21 at 2:08
1  
@JonathanMckibbin Did Robert's answer meet your needs? You should accept it! –  Dustan Levenstein Apr 21 at 2:42

For the sake of contradiction we assume that q is composite. That is, q can be written in the form q = ab, where a,b∈Z with a,b < q. By rules of Legendre Symbols, we know that (q|p) = (ab|p) = (a|p) ∙ (b|p) = -1. That is one of (a|p), (b|p) = -1, and the other is equivalent to 1. That is whichever is equivalent to -1 is a quadratic non residue (mod p) smaller than q, a contradiction. Therefore, q must be prime.

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.