1
$\begingroup$

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.

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

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – gmath Apr 8 '15 at 23:23
  • 1
    $\begingroup$ yes! this is it $\endgroup$ – Elaqqad Apr 8 '15 at 23:24
  • $\begingroup$ It says here that the fact that the Legendre symbol is a homomorphism is given as a hint. How do we use it? @Elaqqad $\endgroup$ – gmath Apr 8 '15 at 23:29
  • $\begingroup$ @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 . $\endgroup$ – Timbuc Apr 9 '15 at 8:18
1
$\begingroup$

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.

$\endgroup$

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.