Taiwan IMO Selection Camp

Throughout this entire solution, all congruence relations are modulo $p$.

Fix $p$, let $\mathcal{P} = \{0, 1, \dots, p-1\}$ be the complete residue system modulo $p$. For all $r \in \mathcal{P}$, let $S_r = \{(a, b) \in \mathcal{P} \times \mathcal{P} : a^2 + b^5 \equiv r\}$, and let $s_r = |S_r|$. Our goal is to prove that for all $r \in \mathcal{P}$, $s_r > 0$.

We will use the known fact that for all congruence classes $r \in \mathcal{P}$ and all positive integers $k$, there exist at most $k$ values $x \in \mathcal{P}$ such that $x^k \equiv r$.

Lemma. Let $N$ be the number of quadruples $(a, b, c, d) \in \mathcal{P}^4$ satisfying $a^2 + b^5 \equiv c^2 + d^5$. Then
$$N = \sum_{r \in \mathcal{P}} s_r^2 \quad (1)$$
and
$$N \le p(p^2 + 4p - 4). \tag{2}$$

Proof.

a. For all congruence classes $r$, there exist exactly $s_r$ pairs $(a, b)$ satisfying $a^2 + b^5 \equiv r$ and $s_r$ pairs $(c, d)$ satisfying $c^2 + d^5 \equiv r$. So there exist $s_r^2$ quadruples satisfying $a^2 + b^5 \equiv c^2 + d^5 \equiv r$. Summing over all $r \in \mathcal{P}$, the result follows.

b. Choose an arbitrary pair $(b, d) \in \mathcal{P}$ and look for possible values of $a, c$.

1. Suppose $b^5 \equiv d^5$, and let $k$ be the number of pairs $(b, d)$. $b$ can be chosen in $p$ different ways. For $b \equiv 0$, $d$ can only be $0$. For nonzero $b$, $d$ has at most five possible values. So we have $k \le 1 + 5(p-1) = 5p-4$.
The values of $a$ and $c$ must satisfy $a^2 \equiv c^2$, so $a \equiv \pm c$, and there exist exactly $2p-1$ such pairs $(a, c)$.

2. Now suppose $b^5 \neq d^5$. In this case, $a$ and $c$ must be distinct. Using $(a-c)(a+c) = d^5 - b^5$, the value of $a-c$ uniquely determines the value of $a+c$, and also determines the values of $a$ and $c$. Therefore, there exist $p-1$ suitable pairs $(a, c)$.

Thus, for the $k$ pairs $(b, d)$ satisfying $b^5 = d^5$, there exist $2p-1$ pairs $(a, c)$, and for the other $p^2-k$ pairs $(b, d)$, there exist $p-1$ pairs $(a, c)$. Therefore,
$$\begin{aligned} N &= k(2p-1) + (p^2-k)(p-1) = p^2(p-1) + kp \\ &\leq p^2(p-1) + (5p-4)p = p(p^2 + 4p - 4). \end{aligned}$$

Suppose that for some $r \in \mathcal{P}$, $S_r = \emptyset$. Clearly $r \neq 0$. Let $T = \{x^{10} : x \in \mathcal{P} \setminus \{0\}\}$. Because every congruence class is the 10th power of at most 10 elements in the set $\mathcal{P}$, from $p > 100$ we obtain $|T| \geq \frac{p-1}{10} \geq 4$.

For all $t \in T$, we have $S_{tr} = \emptyset$. Indeed, if $(x, y) \in S_{tr}$ and $t \equiv z^{10}$, then
$$(z^{-5}x)^2 + (z^{-2}y)^5 \equiv t^{-1}(x^2 + y^5) \equiv r,$$
so $(z^{-5}x, z^{-2}y) \in S_r$. Therefore, among $S_1, \dots, S_{p-1}$ there exist at least $\frac{p-1}{10} \geq 4$ empty sets and among $s_0, s_1, s_2, \dots, s_{p-1}$ there exist at most $p-4$ nonzero numbers. Then by the $AM-QM$ inequality, we obtain
$$N = \sum_{r \in \mathcal{P} \setminus rT} s_r^2 \geq \frac{1}{p-4} \left( \sum_{r \in \mathcal{P} \setminus rT} s_r \right)^2 = \frac{|\mathcal{P} \times \mathcal{P}|^2}{p-4} = \frac{p^4}{p-4} > p(p^2+4p-4),$$
which, by the Lemma, cannot be true.