Prove $r$ the smallest quadratic non-residue modulo $p \geq 3$ is prime

Question

I've been struggling to find the solution for this question for a while now and thought I might as well ask for some help. The question is:

Let $r$ be the smallest positive quadratic non-residue modulo $p \geq 3$, that is, the smallest positive integer $r$ for which the congruence $x^2 \equiv r \enspace (\textrm{mod} \enspace p)$ has no solution. Prove that r is a prime number.

Any help is appreciated. Thank you!

Answer 1

Suppose for contradiction that $r$, the smallest positive non-residue of $p$ is not a prime number. Then $r$ is a composite number greater then $1$. That means that $r$ has two factors $s$ and $t$ such that $s<r$ and $s<t.$ If $s$ and $t$ were both quadratic residues then $r$ would also be a quadratic residue. But $r$ is not a quadratic residue so either $s$ or $t$ must be a quadratic non-residue. Now we have found a positive non-residue mod $p$ that is smaller than $r$, which is a contradiction.

Answer 2

Assume neither $a$ nor $b$ are multiples of $p$.

$$(ab/p)=-1\rightarrow(a/p)(b/p)=-1$$

So if a composite number is a non-residue, it has a proper factor that is a non-residue. Therefore, the minimum non-residue must be prime.