Prove that there are quadratic residues that differ by 6

Question

Let $p \geq 19$ be a prime number. Prove that in the set $\{1,..., p-1\}$ there exist two quadratic residues (QR) that differ by 6.

My attempt: If 2 is a QR, then (2,8) is solution.

If 3 is QR, then (3,9) is solution, since 9 is a complete square.

If 2 is not QR and 3 is not QR, then 6 is QR and 12 is not a QR, so (6,12) and (12,18) are not a solution. If 5 is not a QR, then 10 is (since 2 and 5 are not QR) and (4,10) is solution. If 5 is QR, then 10 and 15 are not QR.

Then I consider 7, 11, 13, but couldn't proceed. Can someone help, at least give a hint? Thanks a lot in advance.

Answer 1

(This assumes that we're treating $ \{ 1, 2, \ldots, p-1 \}$ as actual integers, not as residue classes. In particular, the difference between $p-2$ and $4 $ is $ p - 6 \neq 6$.)

Simply continue from where you left off with the case of "Suppose that $ 2, 3$ are NQR, then QR are $1, 4, 6, 9, 16$ and NQR are $ 2, 3, 8, 12, 18$."

Hint: Wisely hunt down the QR/NQR status for the rest of the values: $5, 7, 10, 11, 13, 14, 15, 17$.
I can't do much with 5 as yet, but I can use $ 7 = 1 + 6$ to show that $ 7$ is not QR.
That's my first step, try to figure out the rest before looking at the hidden text. (Of course, there could be other paths to complete this.)

My steps:

• Show that if $ 7 $ is a QR, then we are done. So 7 is NQR, 14 is QR.

Show that the statement is true for $ p = 19$. Henceforth, assume that $ p \geq 23$. 21 is NQR, and we have to hunt down the QR/NQR status of $19, 20, 22$.

Show that if 20 is QR then we are done. So 20 is NQR, 5 is NQR.

Then, $ 2 \times 5 = 10$ and 16 are QR. Thus we are done.

---

Notes

• I didn't like excluding $ p = 19$, but the (14,20) pair is very useful and came up in multiple paths.
• For the first 18 integers, we could have QR of 1, 4, 5, 9, 13, 14, 16, 17 and NQR of 2, 3, 7, 8, 10, 11, 12, 15, 18, with no apparent contradiction (to me), so I needed to push past 19.
• We can show that $-1$ is QR. But I couldn't find a way to use that.
• I listed the shortest path I could find. There are multiple paths, and any of them will work.

Answer 2

As the OP observes, we may assume $\left(2\over p\right)=-1$, since otherwise we immediately have $\left(2\over p\right)=\left(8\over p\right)=1$. Likewise we can assume $\left(7\over p\right)=-1$, since otherwise we immediately have $\left(1\over p\right)=\left(7\over p\right)=1$. Finally, we can assume $\left(5\over p\right)=1$, since otherwise we immediately have $\left(4\over p\right)=\left(10\over p\right)=\left(2\over p\right)\left(5\over p\right)=1$.

But all these assumptions now tell us that $\left(14\over p\right)=\left(20\over p\right)=1$, so it remains to check, for $p=19$, that $\left(1\over19\right)=\left(7\over19\right)=1$ (and/or $\left(11\over19\right)=\left(17\over19\right)=1$).

Remark: One might also invoke the assumption $\left(-1\over p\right)=1$, since otherwise we immediately have $\left(p-8\right)=\left(p-2\over p\right)=-\left(2\over p\right)=1$. Doing so would rule out $p=19$ without the need to explicitly exhibit a pair of quadratic residues for it.

Additional remark: The heart of the argument here can be expressed as saying that

$$\left(1+\left(1\over p\right)\right)\left(1+\left(7\over p\right)\right)+\left(1+\left(2\over p\right)\right)\left(1+\left(8\over p\right)\right)+\left(1+\left(4\over p\right)\right)\left(1+\left(10\over p\right)\right)+\left(1+\left(14\over p\right)\right)\left(1+\left(20\over p\right)\right)$$

is greater than or equal to $4$. This can be demonstated directly by simplifying the various Legendre symbols (e.g., $(1/p)=(4/p)=1$, $(8/p)=(2/p)$, etc.), expanding, simplifying some more, and recollecting the expression into the form

$$4+\left(1+\left(2\over p\right)\right)\left(1+\left(5\over p\right)\right)+\left(1+\left(2\over p\right)\right)\left(1+\left(7\over p\right)\right)+\left(1+\left(7\over p\right)\right)\left(1+\left(10\over p\right)\right)$$

Answer 3

Why do you insist that $p \geq 19$? The task works for all primes below $19$ except for $p=5$: for $p = 17$, $8-2 = 6$ with $8 = 5^2$ and $2 = 6^2$, for $p = 13$ use $10-4 = 6$, for $p = 11$ use $4 - 9 = 6$, for $p = 7$ use $1 - 2 = 6$, for $p = 3$ use $1 - 1 = 6$, and for $p = 2$ use $1-1 = 6$. When $p = 5$, the quadratic residues are $1$ and $4$, and these don't differ by $6 \bmod 5$ in either order.

I assume by "quadratic residue" mod $p$ you mean a nonzero square mod $p$. Let's show for each prime $p \geq 7$ and each $c \not\equiv 0 \bmod p$ that there are quadratic residues mod $p$ that differ by $c$. This task will be turned into solving for points on a hyperbola mod $p$, which has lots of solutions.

We want to show the congruence $y^2 - x^2 \equiv c \bmod p$ has a solution with $x, y \not\equiv 0 \bmod p$. Rewrite the congruence as $(y-x)(y+x) \equiv c \bmod p$ and make the change of variables $u = y-x$ and $v = y+x$ (this is invertible since $2 \bmod p$ has an inverse). Then you're trying to solve $uv \equiv c \bmod p$ with $u \not\equiv \pm v \bmod p$: avoiding $x \equiv 0 \bmod p$ and $y \equiv 0 \bmod p$ in the original congruence corresponds to $u \equiv v \bmod p$ and $u \equiv -v \bmod p$.

Since $p$ is prime and $c \not\equiv 0 \bmod p$, the congruence $uv \equiv c \bmod p$ has $p-1$ solutions. A solution with $u \equiv v \bmod p$ can only occur if $c \bmod p$ is a quadratic residue, in which case such a solution occurs only twice, and a solution with $u \equiv -v \bmod p$ can only occur if $-c \bmod p$ is a quadratic residue, in which case such a solution occurs only twice. That means for each nonzero $c \bmod p$ there are at most four "forbidden" solutions to $uv \equiv c \bmod p$, so as long as $p-1 > 4$ there is a solution where $u \not\equiv \pm v \bmod p$. Thus for prime $p \geq 7$ and $c \not\equiv 0 \bmod p$, there are quadratic residues mod $p$ with difference $c$. The inequality $p \geq 7$ is sharp because for the prime $5$ the only nonzero differences of quadratic residues are $2$ and $3$: quadratic residues mod $5$ can't differ by $1 \bmod 5$, as we saw at the start.

The situation would be more complicated if you ask about a quadratic residue and quadratic nonresidue mod $p$ with a given difference or two quadratic nonresidues mod $p$ with a given difference.

Answer 4

There is a simpler way to see this though.

Let us assume that $p>20$ [one can check $p \le 19$ directly], and that there are no numbers $i,j \in \{1,\ldots, p-1\}$ such that $i$ and $j$ are both quadratic residues and $i-j=6$.

What about $5$. Now, if $5$ is a quadratic residue, then $20$ is a quadratic residue, which gives $14$ must not be a quadratic residue otherwise we would arrive at a contradiction. So $14$ must not be a quadratic residue, which gives one of $2,7$ must be a quadratic residue. So either $(2,8)$ are a pair of quadratic residues or $(1,7)$ are a pair of quadratic residues, which is either way a contradiction.

Now, if $5$ not a quadratic residue, then either $2$ is a quadratic residue, or $2 \times 5=10$ is a quadratic residue. If $2$ is a quadratic residue then $(2,8)$ are a pair of quadratic residues. If $10$ is a quadratic residue then $(4,10)$ are a pair of quadratic residues. Either way it is a contradiction.