Nemotron-IMO-Bench 2026 N31

Let $p>2$ be a prime and let $a_1, a_2,...,a_p$ be integers. Prove that there is a polynomial $P$ with integer coefficients, of degree $\leq \frac{p-1}{2}$ such that $P(i) \equiv a_i \pmod p$ for all $1 \leq i \leq p$ if and only if for all $1\leq d \leq \frac{p-1}{2}$ we have $$\sum_{i=1}^p (a_{i+d} - a_i )^2 \equiv 0 \pmod p,$$ where indices are taken modulo $p$.