Why does this inequality hold for smallest positive non-square modulo p? 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.
