# Least quadratic nonresidue modulo $p$ is a prime.

Let $p$ be an odd prime. Then, show that the least quadratic nonresidue modulo $p$ is a prime. As a hint is given the fact that Legendre symbol is a homomorphism.

• Not only is $\;1\;$ not a prime: it also is not a quadratic non-residue for any prime. – Timbuc Apr 8 '15 at 23:18
• You should probably lookup the meaning of the word consequently :-) – Mariano Suárez-Álvarez Apr 8 '15 at 23:18

Hint: let $\;a\;$ be the least quadratic non-residues (=QNR) for some prime $\;p\;$ . If $\;a=bc\;$ then it must be that exactly one of $\;b,\,c\;$ is a QNR, thus getting a contradiction.

Hint let $n$ be the least quadratic non residue $\mod p$, assume that $n=ab$ is not a prime then $a,b<n$ so $a$ and $b$ must be quadratic residus it follows that $\cdots\cdots$, contradiction,

As requested we can use the fact that the Legendre symbol is an homomorphism, in fact given a composite element $x=ab$ with $a,b< x$ then: $$\left( \frac{a}{p} \right)\left( \frac{b}{p} \right)=\left( \frac{x}{p} \right)$$ and as consequence $x$ can not be the least quadratic non residue

• It follows that since we firstly assumed that n is the least quadratic non-residue mod p then neither a nor b can be one so contradiction right ?? @Elaqqad – gmath Apr 8 '15 at 23:23
• yes! this is it – Elaqqad Apr 8 '15 at 23:24
• It says here that the fact that the Legendre symbol is a homomorphism is given as a hint. How do we use it? @Elaqqad – gmath Apr 8 '15 at 23:29
• @DI... Exactly as hinted here and in the other answers: the product of QNR is a QR, and of course the product o QR is a QR . – Timbuc Apr 9 '15 at 8:18

Apply the Lemma to the set $\,S\,$ of naturals that are quadratic residues mod $\,p.$

Lemma $\$ If $\,\{1\}\subsetneq S\subsetneq \Bbb N$ is closed under multiplication then the least $\,n\not\in S\,$ is prime.

Proof $\$ Else $\, n = ab,\,\ 1 < a,b < n\,$ so $\,a,b\in S\,\Rightarrow\, ab \in S,\,$ contradiction.