There exists $a$ s.t the 2 equations both have integer solutions.

Question

For each prime $p>5$, prove that there always exists an integer $a$ s.t the two following equations $$x^2+py+a=0\quad\text{and}\quad x^2+py+a+2=0$$ both have integer solutions.

Here are my thoughts for this problem:
$x^2+py+a=0\iff x^2+a\equiv 0\pmod{p}$ and $m^2+pn+a+2=0\iff m^2+a+2\equiv 0\pmod{p}.$
So if there exists an integer $a$ s.t $\left(\dfrac{-a}{p}\right)=\left(\dfrac{-a-2}{p}\right)=1$ then we finish.
But I don't know whether such $a$ exists. Could someone help me or have another way to deal with this problem? Thanks in advance!

Answer 1

You have made a good start on a valid approach. To prove an integer $a$ always exists, consider several special cases. For $a = -1$, since $\left(\frac{-a}{p}\right) = \left(\frac{1}{p}\right) = 1$ for all primes, check when $\left(\frac{-a-2}{p}\right) = \left(\frac{-1}{p}\right) = 1$. By $q = \pm 1$ and the first supplement, we have that $p \equiv 1 \pmod{4}$ works.

Thus, we have only $p \equiv 3\pmod{4}$ left, which can be handled with $p \equiv 3\pmod{8}$ and $p \equiv 7\pmod{8}$ separately. With $a = 0$ satisfying the first Legendre symbol, we need $\left(\frac{-a-2}{p}\right) = \left(\frac{-2}{p}\right) = 1$. By $q = \pm 2$ and the second supplement (also in Show that there exists $a \in \mathbb{Z}$ s.t $a^2 \equiv -2 \pmod p$.), we have $p \equiv 1, 3\pmod{8}$, so this covers the $p \equiv 3\pmod{8}$ case. With $a = -4$ satisfying the first value, then for $\left(\frac{-a-2}{p}\right) = \left(\frac{2}{p}\right) = 1$, by $q = \pm 2$ and the second supplement again, we have $p \equiv 1, 7\pmod{8}$, so this covers the remaining $p \equiv 7\pmod{8}$ case.

Note the table in Law of quadratic reciprocity also has these results. In addition, you could use quadratic reciprocity or other means to determine other sets of $a$ values which cover all of the odd primes $p$.

Answer 2

There is a combinatorial way of doing this, for those who know basic graph theory, that uses far less number theory as well. Indeed, we need just the following:

Lemma 1: Let $C$ be a cycle and let $A$ be a subset of the vertices of $C$ s.t. $A$ is more than half the vertices of $C$. Then at least two vertices in $A$ are adjacent in $C$.

To see Lemma 1, start by drawing say a cycle $C$ on $5$ vertices and observing that, if $A$ be any subset of $3$ vertices, then at least two vertices in $A$ have to be adjacent to each other in $C$. Then try for $C$ w $7$ vertices and $A$ with $4$ vertices. $\surd$

Let $C$ be the graph on the elements of $\mathbb{Z}/p\mathbb{Z}$ where two integers $i$ and $j$ are adjacent if $i-j$ is in $\{-2,2\}$, or equivalently, either $j=i+2$ or $i=j+2$. Then note that $C$ is a cycle on the $p$ vertices of $\mathbb{Z}/p\mathbb{Z}$, because $\gcd(p,2)$ is $1$.

Next, let $A$ be the elements $a$ in $\mathbb{Z}/p\mathbb{Z}$ such that $-a$ is a square residue.

Then to prove this result, note that it suffices to show that there are two elements in $A$ adjacent to each other in $C$. However, $|A| = \frac{p+1}{2}$ i.e., larger than half the vertices in $C$ which is a cycle. [You did learn that half of the elements in $(\mathbb{Z}/p\mathbb{Z})^×$ plus $\{0\}$ form the set of square residues, right?] So two vertices in $A$ have to be adjacent to each other in $C$, by Lemma 1. And so that gives the desired result. ■

---

Can you generalize? What if you wanted to show that there is an $a \in \mathbb{Z}/p\mathbb{Z}$ such that both $a$ and $a+3$ are square residues? What about the existence of an $a\in \mathbb{Z}/p\mathbb{Z}$ such that both $a$ and $a+c$ are both square residues, for all $c$ s.t. $\gcd(p,c)=1$?