Problem

Source: 2021 Bosnia Herzegovina MO p2, posted as TST inside contest collections, 13.6.2021

Tags: number theory, divisible



Let $p > 2$ be a prime number. Prove that there is a permutation $k_1, k_2, ..., k_{p-1}$ of numbers $1,2,...,p-1$ such that the number $1^{k_1}+2^{k_2}+3^{k_3}+...+(p-1)^{k_{p-1}}$ is divisible by $p$. Note: The numbers $k_1, k_2, ..., k_{p-1}$ are a permutation of the numbers $1,2,...,p-1$ if each of of numbers $1,2,...,p-1$ appears exactly once among the numbers $k_1, k_2, ..., k_{p-1}$.