Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
up vote 5 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|cite|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? – User011123521 Apr 21 '14 at 2:01
Because if $a$ or $b$ is a nonresidue, $q$ wasn't the smallest nonresidue. – Robert Israel Apr 21 '14 at 2:06
Oh thank you! Slipped right passed me. – User011123521 Apr 21 '14 at 2:08
@JonathanMckibbin Did Robert's answer meet your needs? You should accept it! – Dustan Levenstein Apr 21 '14 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|cite|improve this answer

Your Answer


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.