Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

1 Answer 1

up vote 1 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|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

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.