Let $p$ an odd prime, $s$ the smallest integer quadratic non residue modulo $p$. Prove that $p > 2s^2-s$ if $-1$ is quadratic residue modulo $p$.

Question

I'm suffering with a number theory question.

Let $p$ an odd prime, $s$ the smallest integer quadratic non-residue modulo $p$. Suppose $p > 5$ and $-1$ is a quadratic residue modulo $p$; then

$p > 2s^2-s$.

I already proved that for any $p$ odd $p > s^2-s$. (proof sketch: Let $q$ be the smallest positive integer such that $sq > p$ , and $r= sq-p$. Since $p$ is prime, $1<r<s$. Using Legendre symbols I could find that $q$ is a quadratic non-residue, so $q \ge s$ and then $p > s^2-s$).

Following the extra information, using Euler's criterion, $p = 4n+1$. Unfortunately I have no clue how to use this piece of information.

Answer 1

The problem asks to prove that

$$p \gt 2s^2 - s \tag{1}\label{eq1}$$

where $p$ is a prime $\gt 5$, $-1$ is a quadratic residue and $s$ is the smallest non-quadratic residue.

Consider the case where $2$ is not a quadratic residue. Thus, $s = 2$ so $2s^2 - s = 6$, giving that all primes $p \gt 5$ satisfy \eqref{eq1}.

Next, consider $2$ is a quadratic residue, so $s \ge 3$. Also, since $-1$ is also a quadratic residue, this means that so is any $0 \lt n \lt s$ times $p - 1$ as it's the product of $2$ quadratic residues. As such, apart from $p$ itself, all integers from $p - (s - 1)$ to $p + (s - 1)$, inclusive, are quadratic residues. This forms a contiguous range of $2s - 1$. Including $p + s$, this forms a range of $2s$. Similar to what the question suggests, this means there exists an integer $q$ such that $2qs$ is within this range. Note that $2qs = p$ can't be true. Also, if $2qs = p + s$, then $s\left(2q - 1\right) = p$, which can't be the case. As such, we get that

$$p - s \lt 2qs \lt p + s \tag{2}\label{eq2}$$

Since all of the values in this range, apart from $p$, are quadratic residues, then so is $2qs$. Since $2$ is a quadratic residue, but $s$ is not, then $q$ can't be as well. Thus, $q \ge s$. Using this in the right-hand part of \eqref{eq2}, we get

$$p + s \gt 2qs \ge 2s^2 \Rightarrow p \gt 2s^2 - s \tag{3}\label{eq3}$$

As such, \eqref{eq1} is also true in this case.