2
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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 \\ $\endgroup$
    – Will Jagy
    Jan 29, 2019 at 1:15
  • 2
    $\begingroup$ 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. $\endgroup$
    – Gralha
    Jan 29, 2019 at 10:11

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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$. $\endgroup$ Jan 20, 2020 at 18:19
  • $\begingroup$ @RafaelDeiga You're correct. Thanks for spotting the typo & pointing it out to me. I've now fixed it. $\endgroup$ Jan 20, 2020 at 18:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .