Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 (#4)

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

share|cite|improve this question
Which parts did you not understand? The solution that you linked to provides the necessary details. – Calvin Lin Sep 28 '13 at 1:09
up vote 1 down vote accepted

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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