Q:

Let p be an odd prime, q the smallest quadratic non residue (mod p). Prove q is prime.

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. 

A:

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

