

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

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$.

share|cite|improve this question
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's_little_theorem and'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
up vote 3 down vote accepted

If it is odd, each n can be paired with -n. So we get $n^m+(-n)^m=n^m-n^m=0$

share|cite|improve this answer
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
Ah, there we go. That was the thing I was missing. Thanks! – Eugene Bulkin Aug 29 '10 at 0:58

Your Answer


