Find all natural numbers $n$ that divide $1^n + 2^n + \cdots+ (n-1)^n$ Problem: Find all natural numbers $n$ that divide $1^n + 2^n + \cdots + (n-1)^n$
Actually, this isn't homework, but I'll add a homework tag just in case. The problem is from Santos' Number theory for mathematical contests. I don't know where to start from to solve this problem. Absolutely nothing comes to my mind at the moment.
 A: As Peter Tamaroff pointed out, the question is ambiguous. The problem could be interpreted as $1^n+2^n+\cdots+(n-1)^n\equiv 0\mod n$ or $1^n+2^n+\cdots+(n-1)^n\equiv 0\mod m$. If the first interpretation is correct then the answer is as follows:
$n$ is either odd or even, if it's odd, then the problem is actually quite easy:
1) $n=2k+1$ for some k:
$1^n+2^n+\cdots+(n-1)^n\equiv 0\mod n \iff 1^n+2^n+\cdots+(n-1)^n\equiv 1^n + 2^n + \cdots (-2)^n + (-1)^n \mod n$ because $n-1 \equiv -1 \mod n$, $n-2 \equiv -2 \mod n$ and so forth.. Also, since $n=2k+1$, the number of terms of $1^n+2^n+\cdots+(n-1)^n$ will be even and all the terms will get canceled in pairs. Therefore, we'll always have $1^n+2^n+\cdots+(n-1)^n\equiv 0 \mod n$ in this case and all odd numbers are accepted.
2) $n=2k$ for some k:
We claim that there is no solution in this case, but we have to consider two different cases where $k=2l$ or $k=2l+1$.
a) If $k=2l+1$ is indeed odd, then the proof is easy and straightforward as follows:
Let $1^{2k}+2^{2k}+\cdots+(2k-1)^{2k}\equiv 0\mod 2k$. That means $2k \mid 1^{2k}+2^{2k}+\cdots+(2k-1)^{2k}$, but that implies $2 \mid 1^{2k}+2^{2k}+\cdots+(2k-1)^{2k}$, i.e. :
$1^{2k}+2^{2k}+\cdots+(2k-1)^{2k} \equiv 0 \mod 2$, but since the number of terms in this case are odd, we can always find a middle term and isolate it. The other terms will get doubled because $ 1^{2k} \equiv (2k-1)^{2k} \mod (2k) $ and so forth.. Therefore, only the middle term will remain because the rest of the terms are divisible by 2.. and the middle term will be $k=2l+1$ which is odd, and we know that an odd number raised to any power remains odd. therefore $ 1 \equiv 0 \mod 2$ and that's contradiction. Therefore, there are no solutions when $n$ is even and $k$ is odd.
b) Now suppose $n=2k$ and $k$ is even. We can rewrite $n$ as $n=2^mt$ where $2 \nmid t$ by factoring out powers of 2 out of $k$. First of all, observe that:
$\Large \forall n \in \mathbb{N}: n < 2^n$
We can use this fact to see that:
$\Large 2^m \mid 2^{2^m} \mid 2^{2^mt} \mid (2s)^{2^mt} \mid (2s)^{n}$ where $2s$ is an even term of $1^n+2^n+\cdots+(n-1)^n$. That forces all even terms of $1^n+2^n+\cdots+(n-1)^n$ to vanish to zero $\mod 2^m$. Therefore, only the odd terms of $1^n+2^n+\cdots+(n-1)^n$ will remain non-zero $\mod 2^m$. But $\varphi(2^m) = 2^m - 2^{m-1} = 2^{m-1}$ and since $a^{\varphi(n)} \equiv 1 \mod n$ we'll have:
$\Large 1^n+2^n+\cdots+(n-1)^n \equiv (1)^{2^mt} + (3)^{2^mt} + \cdots + (2^mt-1)^{2^mt} \equiv (1^{2^{m-1}})^{2t} + (3^{2^{m-1}})^{2t} + \cdots + ((2^mt-1)^{2^{m-1}})^{2t} \equiv (1)^{2t}+(1)^{2t}+\cdots+(1)^{2t} \equiv (2^{m-1}t)\cdot(1) \not\equiv 0 \mod 2^m $
Because $ 2 \nmid t$ and $2^{m-1} \nmid 2^m$ and there are $2^{m-1}t$ terms that all become $1$.
That proves $2^m \nmid 1^n+2^n+\cdots+(n-1)^n$ when $n=2^mt$. Therefore this case is also settled.
This means that our statement is true only when $n$ is an odd number. I hope that my proof is now correct and complete.
Now, is it possible to solve the other interpretation?
