IMC 2023 · Day 1 · P4

Hint: Consider $\prod\limits_{i=0}^{p-1} (i^k + i)$.

First observe that $p = 2$ does not satisfy the condtion, so $p$ must be an odd prime.

Lemma. If $p > 2$ is a prime and $\mathbb{F}_p$ is the field containing $p$ elements, then for any integer $1 \le n < p$ one has the following equality in the field $\mathbb{F}_p$ $$\prod_{\alpha \in \mathbb{F}_p^*} (1 + \alpha^n) = \begin{cases} 0, & \text{if } \frac{p-1}{\gcd(p-1, n)} \text{ is even} \\ 2^n, & \text{otherwise} \end{cases}$$ Proof. We may safely assume that $n | p - 1$ since it can be easily proved that the set of $n$-th powers of the elements of $\mathbb{F}_p^*$ coincides with the set of $\gcd(p-1, n)$-th powers of the same elements. Assume that $t_1, t_2, \dots, t_n$ are the roots of the polynomial $t^n + 1 \in \mathbb{F}_p[x]$ in some extension of the field $\mathbb{F}_p$. It follows that $$\prod_{\alpha \in \mathbb{F}_p^*} (1 + \alpha^n) = \prod_{\alpha \in \mathbb{F}_p^*} \prod_{i=1}^{n} (\alpha - t_i) = \prod_{i=1}^{n} \prod_{\alpha \in \mathbb{F}_p^*} (\alpha - t_i) = \prod_{i=1}^{n} \prod_{\alpha \in \mathbb{F}_p^*} (t_i - \alpha) = \prod_{i=1}^{n} \Phi(t_i),$$ where we define $\Phi(t) = \prod_{\alpha \in \mathbb{F}_p^*} (t - \alpha) = t^{p-1} - 1$. Therefore $$\prod_{\alpha \in \mathbb{F}_p^*} (1 + \alpha^n) = \prod_{i=1}^{n} (t_i^{p-1} - 1) = \prod_{i=1}^{n} \bigl( (t_i^n)^{\frac{p-1}{n}} - 1 \bigr) = \prod_{i=1}^{n} \bigl( (-1)^{\frac{p-1}{n}} - 1 \bigr) = \begin{cases} 0, & \text{if } \frac{p-1}{n} \text{ is even} \\ 2^n, & \text{otherwise} \end{cases}$$ Let us now get back to our problem. Suppose the numbers $i^k + i$, $0 \le i \le p-1$ form a complete residue system modulo $p$. It follows that $$\prod_{\alpha \in \mathbb{F}_p^*} (\alpha^k + \alpha) = \prod_{\alpha \in \mathbb{F}_p^*} \alpha$$ so that $\prod_{\alpha \in \mathbb{F}_p^*} (\alpha^{k-1} + 1) = 1$ in $\mathbb{F}_p$. According to the Lemma, this means that $2^{k-1} = 1$ in $\mathbb{F}_p$, or equivalently, that $2^{k-1} \equiv 1 \pmod p$. Therefore $a_2 = 2^k + 2 \equiv 4 \pmod p$ so that the remainder of $a_2$ upon division by $p$ is either 4 when $p > 3$ or is 1, when $p = 3$.