# 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$.

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. 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.

• printing just primes 1 mod 4 when the smallest nonresidue increases: 5 2 2 s^2 - s: 6 \\ 17 3 2 s^2 - s: 15 \\ 73 5 2 s^2 - s: 45 \\ 241 7 2 s^2 - s: 91 \\ 1009 11 2 s^2 - s: 231 \\ 2689 13 2 s^2 - s: 325 \\ 8089 17 2 s^2 - s: 561 \\ 33049 19 2 s^2 - s: 703 \\ 53881 23 2 s^2 - s: 1035 \\ 87481 29 2 s^2 - s: 1653 \\ – Will Jagy Jan 29 at 1:15
• Out of curiosity, as this seems like a potentially quite difficult problem to solve, where does it come from? – John Omielan Jan 29 at 3:50
• Note using that $-1$ is a quadratic residue, the largest non-quadratic residue is $p - s$. Thus, using what you've proven so far, i.e., $p \gt s^2 - s$, since $s^2 - s = s\left(s - 1\right)$ is a non-quadratic residue, then $s\left(s - 1\right) \le p - s$ which gives that $p \ge s^2$, but as $p$ is prime, then $p \gt s^2$. This is the best I can do so far. – John Omielan Jan 29 at 6:20
• It come from BROCHERO, F., MOREIRA, C.G., SALDANHA, N., TENGAN, E. – Teoria dos números – um passeio pelo mundo inteiro com primos e outros números familiares, Projeto Euclides, IMPA, 2010, chapter 2, section 2.2. In this section we should learn second degree congruences, gauss lemma, law of quadratic reciprocity e legendre/jacobi symbols. – user1553045 Jan 29 at 10:11
• Thanks for providing the reference. I hope somebody can help you more than Will Jagy and I have so far. – John Omielan Jan 29 at 11:28

## 1 Answer

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.