3
$\begingroup$

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.

$\endgroup$

2 Answers 2

Reset to default
5
$\begingroup$

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

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

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .