Belarus — Selection and Training Session

Denote the set of all residues modulo $p$ by $\mathbb{F}_p$. Fermat's little theorem implies that the roots of the polynomial $x^{p-1} - 1$ are all nonzero elements of $\mathbb{F}_p$. Since $x^{p-1} - 1 = (x^d - 1)(x^{d(m-1)} + x^{d(m-2)} + \dots + x^d + 1)$ where $p-1 = md$, the polynomial $x^d - 1$ divides $x^{p-1} - 1$. In this equality the sum of the degrees of the factors equals the number of roots, hence $x^d - 1$ has $d$ roots. Denote these roots $a_1, a_2, \dots, a_d$.

Consider all polynomials of the form $x^d - C$. If such polynomial has a root $b$ then it has $d$ roots $a_1b, a_2b, \dots, a_db$ and cannot have more roots than its degree, so it has exactly $d$ roots. On the other hand, each $b \in \mathbb{F}_p \setminus \{0\}$ is a root of such polynomial, namely $x^d - b^d$. Therefore $\mathbb{F}_p \setminus \{0\}$ is the disjoint union of $m$ sets, consisting of $d$ roots of some polynomial $x^d - C$. Such partition satisfies the problem condition since by Vieta's theorem the sum of the roots and the sum of the pairwise products of the roots of $x^d - C$ are congruent to zero modulo $p$, whence the sum of their squares is likewise congruent to zero.