Show that the smallest quadratic non residue of an odd prime p is itself prime. Hint: Assume to the contrary and use Legendre Symbols
Assume not so let $\displaystyle n $ be the smallest QNR such that $\displaystyle n=ab $. Then $\displaystyle -1=\left(\frac{n}{p}\right)=\left(\frac{ab}{p}\righ t) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right) = (1)(1) = 1 $ since $\displaystyle a,b < n $. Hence a contradiction.