# Existence of Quadratic Non-Residues less than square root of a prime

I had a homework question that I was unable to solve even after the solutions were released!

If $p$ is a prime $\ne 3, 7, 23$ then there is a quadratic nonresidue $\le \sqrt{p}$

I noticed that with very few quadratic residues $\lt \sqrt{p}$ I would be able to construct many more by multiplying them together. I was hoping to use this to get a contradiction by creating $\gt p/2$ quadratic residues but I stalled at a conjecture that turned out to be false. Given the first N integers, how many large prime factors can I disallow and still have half the set remaining?

I cannot follow most of the solution given at http://www.math.nyu.edu/~tschinke/teaching/Fall13/hw2.pdf (#4)

I would like a better exposition of the answer given in the link, or another elementary solution.

-
Which parts did you not understand? The solution that you linked to provides the necessary details. – Calvin Lin Sep 28 '13 at 1:09

This is essentially a rewrite of the linked solution, just with more details.

For a prime $p$, let $a$ be the smallest QNR. Our goal is to show that $a \leq \sqrt{p}$.
By the division algorithm, $p = qa + r$ where $0 \leq r < a$. Since $p$ is prime and $a \neq p$, hence $r \geq 1$.

Since $a (q+1) = qa+a \equiv a - r \pmod{p}$. Since $0 < a-r < a$ by construction, hence $a-r$ must be a quadratic residue. By the Law of quadratic reciprocity $q+1$ must be a QNR. By the definition of $a$, we know that $a \leq q+1$. Hence, $a^2 \leq a(q+1) = aq+a = p-r+a$.

This is almost close to $a^2 \leq p$, which is what we want. How close are we? We actually have $$a^2 -a + \frac{1}{4} \leq p - r + \frac{1}{4} \leq p - 1 + \frac{1}{4} \Rightarrow a - \frac{1}{2} \leq \sqrt{p - \frac{3}{4} } \Rightarrow a \leq \sqrt{p - \frac{3}{4} } + \frac{1}{2}.$$

This is not yet good enough, so we shall consider the cases where $\sqrt{p} < a \leq \sqrt{ p - \frac{3}{4} } - \frac{1}{2}$.

If $p\equiv 1 \pmod{4}$, then we know that $-1$ is a QR. Since $a-1$ is a quadratic residue by construction, hence $a (a-1)$ is a QNR. Evaluating it, we see that $p-a <a^2 -a \leq p-r$. Since $-1$ is a QR, hence $-a(a-1)$ is a QNR. But, we are given that $r \leq -a(a-1) < a$, which contradicts the minimality of $a$.

If $p \equiv 3 \pmod{4}$, and $p > 49$. Recall that $-1$ is a QNR. Consider the term $(a-1)(a+1)$. We have $p-1 < a^2 -1 \leq p - r + a - 1$, hence when reduced modulo $p$, $0 \leq a^2 - 1 \leq a-r-1 < a$. This tells us that $a^2-1$ is a QR. Since $a-1$ is a QR, thus $a+1$ is also a QR.

Now consider $(a-2)(a+1)$. Since $p-a-2 < (a-2)(a+1) \leq p-r-2$ is the product of 2 QR, it is a QR. Remember that $-1, -2, \ldots -(a-1)$ are all QNR and $p-a-1$ is also a QNR, thus the only possibility for a QR in the range is $p-a$. Hence, we must have $p-a = (a-2)(a+1)$, which gives us $p = a^2 - 2$. Since $(a-2)(a+2) = a^2 - 4 \equiv -2 \pmod{p}$ is a QNR, and $a-2$ is a QR, hence $a+2$ is a QNR. Similarly, since $(a-2)(a+3) = a^2 +a - 6 \equiv a-4 \pmod{p}$ is a QR, hence $a+3$ is a QR. Finally, since $(a-3)(a+3) = a^2 - 9 \equiv -7 pmod{p}$ is a QNR (Recall that $7 \leq \sqrt{p} < a$ is a QR and $-1$ is a QNR), hence $(a-3)$ is a QNR. But that contradicts the assumption that $a$ is the smallest QR.

Now, it remains to check for $p \equiv 3 \pmod{4}$ and $p < 49$. The primes are 3, 7, 11, 19, 23, 31, 43, 47. I leave it to you to verify that the only ones with a QNR that is not smaller than $\sqrt{p}$ are 3, 7, 23. Hence we are done.

-
Wow thanks! It's just a little tricky keeping track of all the inequalities and the changes of view from integers on the real line to integers in mod p. – Mark Sep 28 '13 at 4:53
@Mark I hope there is a nicer approach though. It was pretty ugly working through the solution, and there was very little motivation for the steps that were taken. – Calvin Lin Sep 28 '13 at 4:54
I know! Maybe someday someone will post an elegant solution. Thanks. – Mark Sep 29 '13 at 16:11