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.

  • 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 at 1:15
  • $\begingroup$ Out of curiosity, as this seems like a potentially quite difficult problem to solve, where does it come from? $\endgroup$ – John Omielan Jan 29 at 3:50
  • $\begingroup$ 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. $\endgroup$ – John Omielan Jan 29 at 6:20
  • 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$ – user1553045 Jan 29 at 10:11
  • $\begingroup$ Thanks for providing the reference. I hope somebody can help you more than Will Jagy and I have so far. $\endgroup$ – John Omielan Jan 29 at 11:28

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.