Problem 1459

1. Initial Setup and Assumptions:
Let $p > 7$ be a prime and let $A$ be a subset of $\{0, 1, \ldots, p-1\}$ with size at least $\frac{p-1}{2}$. We need to show that for each integer $r$, there exist $a, b, c, d \in A$, not necessarily distinct, such that $ab - cd \equiv r \pmod{p}$.

2. Normalization:
There exists an $x \in A \setminus \{0\}$. By replacing every element $y$ of $A$ with $yx^{-1} \mod{p}$ and $r$ with $rx^{-2} \pmod{p}$, we can assume that $1 \in A$.

3. **Definition of Set $B$:**
Let $B = \{ab \pmod{p} \mid a, b \in A\}$. Clearly, $A \subseteq B$.

4. **Case Analysis on Size of $B$:**
- If $|B| > \frac{p-1}{2}$, we are done because $B$ would cover all residues modulo $p$, ensuring $ab - cd \equiv r \pmod{p}$ for some $a, b, c, d \in A$.
- Assume $|B| = \frac{p-1}{2}$. Then $|B| = |A| = \frac{p-1}{2}$ and thus $B = A$.

5. Subgroup Structure:
- For $x \in A \setminus \{0\}$, multiplication with $x$ permutes the elements of $A$. Hence, $A \setminus \{0\}$ is a subgroup of $\mathbb{F}_p^*$.
- By Lagrange's Theorem, $|A \setminus \{0\}| \mid p-1$. For $p > 7$, we cannot have $\frac{p-3}{2} \mid p-1$. Therefore, $0 \not\in A$ and $A$ is a subgroup of $\mathbb{F}_p^* \cong \mathbb{Z}/(p-1)\mathbb{Z}$ with $\frac{p-1}{2}$ elements.

6. Quadratic Residues:
The only such subgroup is the subgroup of quadratic residues. Thus, $A = B$ is the set of nonzero quadratic residues.

7. **Handling $r$:**
- If $r \not\equiv \pm 1 \pmod{p}$, choose the quadratic residues $ab = \left(\frac{r+1}{2}\right)^2$ and $cd = \left(\frac{r-1}{2}\right)^2$ from $B$.
- We need to show that there are two non-zero quadratic residues with difference $1 \pmod{p}$ for $p > 7$.

8. Existence of Quadratic Residues with Difference 1:
- Note that there are 3 quadratic residues in $\{1, 2, 3, 4\}$ or 4 quadratic residues in $\{4, 5, 6, 7, 8, 9\}$ or $\frac{p-7}{2}$ quadratic residues in $\{9, 10, \ldots, p-1\}$.
- Therefore, one of these sets contains two quadratic residues with difference $1$.

Thus, for each integer $r$, there exist $a, b, c, d \in A$ such that $ab - cd \equiv r \pmod{p}$.

$\blacksquare$