1
$\begingroup$

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

  • 0
    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 http://en.wikipedia.org/wiki/Fermat's_little_theorem and http://en.wikipedia.org/wiki/Euler's_theorem .2010-08-29
  • 0
    Nope, it's still true for every odd number. See Casebash's answer below.2010-08-29
  • 0
    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$.2010-08-29
  • 0
    Nearly, but not quite, ironic that just a teensy bit of cancellation can so radically change an outcome that is subtle term-wise.2011-07-11

1 Answers 1

3

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

  • 0
    In fact, the sum of $n^r$ should work for any odd value of $r$ regardless of what `m` is2010-08-29
  • 0
    Ah, there we go. That was the thing I was missing. Thanks!2010-08-29