Silk Road Mathematics Competition

For simplicity let's enumerate the statements. (1) $(1^{n-1}+2^{n-1}+\cdots +(n-1{)}^{n-1})+1$ is divisible by $n$ (2) $\frac{n}{p}-1$ divisible by $p$ and $\frac{n}{p}-1$ divisible by $p-1$ Let $n=Ap$. Firstly, observe that $$\sum _{k=1}^{n-1}{k}^{n-1}\equiv \{\begin{array}{llc}-A& (\text{mod }p),& \text{if }n-1\text{ is divisible by }p-1,\\ 0& (\text{mod }p),& \text{if }n-1\text{ is not divisible by }p-1\end{array}$$ The first case is clear, it follows from Fermat's little theorem. And the second can be shown, for instance, as follows: let $g$ be a primitive root by modulo $p$, then $$\sum _{k=1}^{p-1}{k}^{n-1}\equiv \sum _{k=1}^{p-1}(gk{)}^{n-1}\equiv g^{n-1}\sum _{k=1}^{p-1}{k}^{n-1}(\mathrm{mod}p)$$ and $g^{n-1}\not\equiv 1(\mathrm{mod}p)$ implies that ${\sum }_{k=1}^{n-1}{k}^{n-1}\equiv 0(\mathrm{mod}p)$. Suppose that (1) holds. Then either $n-1$ divisible by $p-1$ and $A-1$ divisible by $p$, or $n-1$ divisible by $p-1$ and $1$ divisible by $p$. Therefore, $n-1$ divisible by $p-1$ and $A-1$ divisible by $p$. Hence, $n-1=(p-1)A+A-1$ divisible by $p-1\Rightarrow A-1$ divisible by $p-1$, we obtain (2). Now suppose that (2) holds. $A-1$ divisible by $p\Rightarrow n$ is not divisible by $p^2$, so $n$ is squarefree. $A-1$ divisible by $p-1\Rightarrow p(A-1)=n-1-(p-1)$ divisible by $p-1\Rightarrow n-1$ divisible by $p-1$. Therefore, $$1+\sum _{k=1}^{n-1}{k}^{n-1}\equiv 1-A\equiv 0(\mathrm{mod}p),$$ since $A-1$ divisible by $p$. Because this holds for every prime divisor $p$ of $n$, and $n$ is squarefree, using the Chinese Remainder Theorem, we obtain (1).