I would like to prove (disprove if wrong) the following statement:
For all odd prime numbers except for $p=3,5$ or $13$, there exists an
integer $a>0$ such that both $a^2-4$ and $a^2+4$ are quadratic
non-residue $\bmod p$.
Here is what I have done: suppose that $p \notin \{3,5,13\}$ and consider different cases:
Case I: $p \equiv 3 \bmod 4$. We have $q$ is quadratic residue (QR) iff $-q$ is quadratic non-residue (QNR).
Since $p \neq 5$, then either $5$ is QNR (case I-i) or $5$ is QR (case I-ii).
In case (I-i) there exists $b$ such that $b^2 \equiv -5 \bmod p$ and obviously $-b^2+4 \equiv 3^2 \bmod p$ and $-b^2-4 \equiv 1 \bmod p$, then both $b^2-4$ and $b^2+4$ are QNR. It suffices to take $a=b$.
Consider now case (I-ii). Since $p \neq 13$, then either
(I-ii-1) $13$ is quadratic non-residue (QNR) mod $p$
(I-ii-2) $13$ is quadratic residue (QR) mod $p$
In case (I-ii-1), $65=5\cdot 13$ is QNR and there exists $c$ such that $c^2 \equiv -65 \bmod p$ and obviously $-c^2-16 \equiv 7^2 \bmod p$ and $-c^2+16 \equiv 9^2 \bmod p$.
Let $d=\frac{c}{2}$, $e=\frac{7}{2}$ and $f=\frac{9}{2}$ in $ \mathbb{Z}/p\mathbb{Z}$.
Then $-d^2-4 \equiv e^2 \bmod p$ and $-d^2+4 \equiv f^2 \bmod p$ and both $d^2+4$ and $d^2-4$ are QNR. It suffices to take $a=d$.
In the case (I-ii-2) where both $5$ and $13$ are QR, I don't see how to proceed.
In the case (II) where $p \equiv 1 \bmod 4$, we have $q$ is quadratic residue (QR) iff $-q$ is quadratic residue (QNR) and here again the above method does not seem to work.
I am also interested in any sharp upper bound for the smallest $a$, in terms of $p$.
Thanks for help.
Best Answer
Here is a solution in two steps.
First, we prove that when there is no such $a$, 2 is a QR. This is a bunch of casework, and doesn't work for some small primes. (Specifically for $p=2, 3, 5, 7, 11, 13$.) We can check those separately, and find all three counterexamples that way.
Suppose that 2 is a QNR. Therefore 8 is a QNR, 32 is a QNR, 18 is a QNR.
40 must be a QR or else we find the sequence 32, 36, 40. Therefore 20 is a QNR.
12 must be a QR or else we find the sequence 12, 16, 20. Therefore 24 is a QNR, 48 is a QR, 96 is a QNR.
104 must be a QR or else we find the sequence 96, 100, 104. Therefore 52 is a QNR.
28 must be a QNR or else we find the sequence 24, 28, 32. Therefore 14 is a QR.
22 must be a QR or else we find the sequence 14, 18, 22. Therefore 44 is a QNR.
Now we find the sequence 44, 48, 52.
Second, assuming that $2$ is a QR and there are no cases of $a$ such that $a^2-4$, $a^2+4$ are QNR, we arrive at a contradiction.
If any three consecutive integers $k, k+1, k+2$ follow the pattern QNR, QR, QNR, then the same is true for $4k, 4k+4, 4k+8$ and we are done. So adjacent to any QR is another QR.
If this is true, but no two consecutive integers are ever QNR, then we're also in trouble, because then at least approximately $\frac23$ of the residues mod $p$ are QR.
Suppose that $k, k+1$ are both QNR for some $k$. Then $8k, 8k+8$ are both QNR, so $8k+4$ must be QNR or else $8k, 8k+4, 8k+8$ is the sequence we want. (Note that $8k+4 \not\equiv 0 \pmod p$ because then $8k+8$ could not be QNR.) Therefore $2k, 2k+1, 2k+2$ is a sequence of three consecutive QNRs.
Applying this argument again, we see that $4k, 4k+1, 4k+2, 4k+3, 4k+4$ is a sequence of five consecutive QNRs. Then we get ever-longer sequences like this by iterating the argument. But once we get a sequence longer than $p$, we get a contradiction.