3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Geoff Nov 19 '13 at 3:48
  • $\begingroup$ 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. $\endgroup$ – André Nicolas Nov 19 '13 at 3:53
  • $\begingroup$ +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? $\endgroup$ – Calvin Lin Nov 19 '13 at 14:06
  • $\begingroup$ 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. $\endgroup$ – André Nicolas Nov 19 '13 at 17:08

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.