# Why does this sum mod out to 0?

In making up another problem today I came across something odd. I've been thinking it over and I can't exactly place why it's true, but after running a long Python script to check, I haven't yet found a counter example.

Why is $\sum_{n=1}^{m}{n^m}\equiv 0\mod m$ true for all odd $m \ge 3$? The script showed me that each term for odd $m$ is equivalent to $n$ when taken $\mod m$ (until term $m$), and so the sum would be $\frac{m(m-1)}{2}$ which is obviously $0 \mod m$. What I am unable to understand is why $n^m\equiv n \mod m$ only for odd $m$.

-
The claim in the second paragraph is false in general; it is only true for primes and certain "pseudoprimes." For example, it should be false for m = 15. See en.wikipedia.org/wiki/Fermat's_little_theorem and en.wikipedia.org/wiki/Euler's_theorem . –  Qiaochu Yuan Aug 29 '10 at 0:51
Nope, it's still true for every odd number. See Casebash's answer below. –  Eugene Bulkin Aug 29 '10 at 1:01
Sorry, I meant the claim in the second sentence of the second paragraph. I assume you meant to say $n^m$ is equivalent to $n$ when taken $\bmod m$. –  Qiaochu Yuan Aug 29 '10 at 1:05
Nearly, but not quite, ironic that just a teensy bit of cancellation can so radically change an outcome that is subtle term-wise. –  paul garrett Jul 11 '11 at 21:27
If it is odd, each n can be paired with -n. So we get $n^m+(-n)^m=n^m-n^m=0$
In fact, the sum of $n^r$ should work for any odd value of $r$ regardless of what m is –  Casebash Aug 29 '10 at 0:48