# 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 \\ Jan 29, 2019 at 1:15
• 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. Jan 29, 2019 at 10:11

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.

• I think that the interval in the phrase: "As such, apart from $p$ itself, all integers from $p−s−1$ to $p+s−1$, inclusive, are quadratic residues" is wrong. I think u meant $p-(s-1)$ instead of $p-s-1$. Jan 20, 2020 at 18:19
• @RafaelDeiga You're correct. Thanks for spotting the typo & pointing it out to me. I've now fixed it. Jan 20, 2020 at 18:24