IV математическая олимпиада «Шелковый путь», 2005 год

Пусть натуральное число $n \ge 2$. Докажите, что $(1^{n-1} + 2^{n-1} + \ldots + (n-1)^{n-1}) + 1 \text{ делится на } n$ тогда и только тогда, когда для каждого простого делителя $p$ числа $n$ $\dfrac{n}{p}-1 \text{ делится на $p$ и $\dfrac{n}{p}-1$ делится на $p - 1$}.$