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!
Best Answer
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.