# Consecutive quadratic residues of primes that differ by 2

Show that if $p$ is prime and $p \ge 7$, then there are always two consecutive quadratic residues of $p$ that differ by 2.

I think that I am supposed to use the fact that at least one of $2, 5$ and $10$ is always a quadratic residue however I'm not sure exactly how to link this to the question.

We will show for any prime $p\ge 7$ there are two consecutive positive quadratic residues of $p$ that differ by $2$. The result is easy to verify for the prime $7$. So we suppose that $p\gt 7$.

For brevity we write QR for quadratic residue of $p$, and NR for quadratic non-residue of $p$.

Let $q$ be the smallest positive NR of $p$. Note that $q$ is prime. If $q$ is odd, then $q-1$ and $q+1$ are consecutive QR that differ by $2$, since all their prime factors are $\lt q$.

So we are finished unless $2$ is a NR. Assume $2$ is a NR. If $3$ is a QR, we are finished. So we may assume that $3$ is a NR.

Then $6$ is a QR, and therefore we are finished unless $5$ is a QR. If $7$ is a QR, we are finished, for $8$ is NR and $9$ is QR.

So we have solved our problem unless $2$ is NR, $3$ is NR, $5$ is QR, and $7$ is NR.

But in that case $14$ is QR, $15$ is NR, and $16$ is QR. The result follows.

• Thanks for the reply. I got a little bit lost when trying to follow it at points. For example, why does 3 being NR imply 6 is QR? – Geoff Nov 19 '13 at 3:48
• Remember, we are working on the assumption $2$ is NR, since all other cases were dealt with in the first sentence. So $2$ is NR. If $3$ is also NR, then the product $2\cdot 3$ is QR. Recall the general result that the product of two NR is a QR. We use this fact a couple of other times in the solution, without mentioning it. We also use the fact that a QR times an NR is an NR. – André Nicolas Nov 19 '13 at 3:53
• +1 nice, though I felt certain small steps were missing, and had to fill them in. When saying 5 Ida QR, best to remind the reader that 4 is a QR. do you need p> 13, since you used 16 at the end? – Calvin Lin Nov 19 '13 at 14:06
• Yes, I was leaving little things (squares are QR, stuff about products) out since the question had homework flavour. We definitely do not need $p\gt 13$. In traditional number theory, being a QR is a property of numbers, with a theorem that says that if the numbers $a$ and $b$ are congruent, then $(a/p)=(b/p)$. Anyway, if we are worried about $11$ and $13$ we do not need to solve separately: reduce mod $p$, the numbers $14,15,16$, reduced, remain consecutive. – André Nicolas Nov 19 '13 at 17:08