Q:

Proving q is prime in the Legendre Symbol

Prove that if $p$ is an odd prime and if $q$ is the least integer such that  $0$ < $q$ < $p$ and $\left(\frac qp\right)= -1 $, then q is prime.

I've tried to solve it by contradiction. I assumed that $q$ was a composite and then stated that $q$= $a$ $b$ where $a$ and $b$ are primes and that $$\left(\frac qp\right)= \left(\frac ap\right)\left(\frac bp\right)=-1 $$. So either $\left(\frac ap\right)$ is -1 or $\left(\frac bp\right)$ is -1. I don't know what to do from here onwards and am not sure what I've done so far is correct. A hint in the right direction would be appreciated. Thanks.

A:

First rule out that $q=1$, so that $q \gt 1$.
Then proceed by assuming $q=ab$ unless $q$ is prime, with $1 \lt a,b \lt q \lt p$.
Use the fact that the Legendre symbol is a completely multiplicative function:
$$ \left( \frac{a}{p} \right) \left( \frac{b}{p} \right) = \left( \frac{q}{p} \right) = -1
$$
Now you can use the assumption that $q$ is the least residue mod $p$ which gives a Legendre symbol value of -1 to get a contradiction.  Hence $q$ must be prime.

