Let $p$ be an odd prime and $q$ the smallest positive integer that is not a square modulo $p$. Show that $q<\sqrt{p}+1$?
I can show that $q$ also has to be prime and that $p$ is a divisor of $q^\frac{p-1}{2}+1$. But I am not sure how this can help me.
Assume $q>\sqrt p+1$. Let $a=\left\lceil\frac pq\right\rceil$. Then $$1\le a\le\left\lceil\frac p{\sqrt p+1}\right\rceil =\left\lceil\sqrt p-1+\frac 1{\sqrt p+1}\right\rceil\le\left\lceil\sqrt p\right\rceil<q,$$ hence $a$ is a square $\bmod p$ and so $aq$ is a non-square. But from $p\le aq<p+q$, we see that $aq\bmod p$ is one of $0,1,\ldots,q-1$, hence a square, contradiction.