Balkan Mathematical Olympiad Shortlist

Letting $n = p - 1$, we have $x_i^{p-1} \equiv 0$ or $1 \pmod{p}$. Therefore, the congruence $x_1^n + x_2^n + \dots + x_p^n \equiv 0 \pmod{p}$ is true when either all $x_i$ are divisible by $p$ or no $x_i$ is divisible by $p$.

On the other hand, if no $x_i$ is divisible by $p$ we have
$$\sum_{i=1}^{p} (x_i - x_1)^n = \sum_{j=0}^{n} \left( \sum_{i=1}^{p} x_i^j \right) \binom{n}{j} (-x_1)^{n-j} \equiv 0 \pmod{p}.$$
Hence, $0, x_2 - x_1, x_3 - x_1, \dots, x_p - x_1$ satisfy the condition, so, all $x_i$ are congruent modulo $p$.