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.


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$?

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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