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

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!

• Think about $r$'s prime factorisation. – Lord Shark the Unknown Aug 19 at 4:05

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 and $$s 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.
• You should also rule out the possibility that $r=1$, since $1$ is not a prime but also does not factor into smaller parts. Sure, it’s very easy, but it should be mentioned. – Erick Wong Aug 19 at 4:26
Assume neither $$a$$ nor $$b$$ are multiples of $$p$$.
$$(ab/p)=-1\rightarrow(a/p)(b/p)=-1$$