3
$\begingroup$

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.

$\endgroup$
13
  • $\begingroup$ The first part only depends on $3,$ you don't need $2$ not a QR. $\endgroup$ Jun 8 at 15:54
  • $\begingroup$ Also, if $-2$ is a QR, then $-2$ and $4$ are QR. $\endgroup$ Jun 8 at 15:55
  • 1
    $\begingroup$ You can take $x^2$ and $y^2$, for $x=2^{-1}\cdot5$ and $y=2^{-1}$. For this choice $x+y=2^{-1}\cdot5+2^{-1}=2^{-1}\cdot6=3$ and $x-y=2^{-1}\cdot5-2^{-1}=2^{-1}\cdot4=2$. Therefore, $x^2-y^2=(x+y)(x-y)=3\cdot 2=6$. $\endgroup$
    – plop
    Jun 8 at 15:55
  • $\begingroup$ @CalvinLin We are talking integers modulo $p.$ You can take $p-2.$ $\endgroup$ Jun 8 at 15:59
  • 1
    $\begingroup$ @Ionza But 23 is not in the set $ \{ 1, 2, \ldots 18\}$, so you can't choose 23. I know I'm being slightly pedantic, but I'm picking up on the $ p \geq 19$ condition supposedly being necessary. $\endgroup$
    – Calvin Lin
    Jun 8 at 16:05
5
$\begingroup$

(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.
$\endgroup$
6
  • $\begingroup$ Well, for $p=19$ we do have $\{1,7\}$ where $7$ is actually both a quadratic residue and a cubic one. $\endgroup$ Jun 8 at 16:55
  • $\begingroup$ @OscarLanzi Your statement is true. I'm not sure what point you're trying to make. $\endgroup$
    – Calvin Lin
    Jun 8 at 17:23
  • $\begingroup$ "I didn't like excluding p=19, but the (14,20) pair is very useful and came up in multiple paths." It could have been knocked out as its own case. $\endgroup$ Jun 8 at 17:33
  • $\begingroup$ @OscarLanzi Right, that is what I did. See the first hidden point where I dealth with $ p = 19$ as its own case. $\quad$ To clarify, I would have preferred a solution that didn't need to deal with $ p = 19$ separately. However, I don't think that such a solution exists (with my 2nd note as further justification). $\endgroup$
    – Calvin Lin
    Jun 8 at 17:34
  • $\begingroup$ @CalvinLin Clear, thanks a lot! $\endgroup$
    – user121
    Jun 8 at 18:10
4
$\begingroup$

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)$$

$\endgroup$
2
  • $\begingroup$ Lol I tried the Legendre symbol way too, but didn't push through far with it. (I tried taking the sum from 1 to 18 or 23 or $p-7$, which wasn't easy to manipulate.) I like how you focused just on these terms. $\endgroup$
    – Calvin Lin
    Jun 8 at 20:15
  • $\begingroup$ @CalvinLin, I started out with a long, complicated attempt at showing the entire sum, $\sum_{a=1}^{p-7}\left(1+\left(a\over p\right)\right)\left(1+\left(a+6\over p\right)\right)$, had to be positive. It became a mess and wasn't working. Then I realized the OP had already done most of what needed doing. It was only afterward that I noticed that the approach that worked amounted to looking at only four terms of the sum. $\endgroup$ Jun 8 at 20:20
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.