I have this question posted by professor in graduate Number Theory class. First he asked for proof that the sum of cube of 3 consecutive integers is divisible by 3, which is very easy to prove, but then he continued by asking to prove its generalization, ie., n | 1^n + 2^n + 3^n + … + n^n.
Here you can easily find a counterexample that if n is even, the generalization fails. But if n is odd, looks like it works. I tried using mathematical induction but did not go anywhere. Then I tried using Binomial Expansion, Pascal Triangle, and using representation of consecutive numbers as … (a-3), (a-2), (a-1), a, (a+1), (a+2), (a+3), … in order to cancel out, but still did not go anywhere.
I would appreciate any help. Thank you for your time.
Best Answer
Since this is a graduate level number theory class, I think it's safe to assume that you are familiar with modulo arithmetic?
Given any list of $n$ consecutive integers, $a, a+1, a+2, \dots, a+n-1$, modulo $n$ this list is equivalent to $0,1,2,3,\dots,n-1$ modulo $n$. (Note that I am not saying $a \equiv 0 \pmod{n}$). This list can be rewritten as:
$1 \equiv 1 \pmod{n}$
$2 \equiv 2 \pmod{n}$
$3 \equiv 3 \pmod{n}$
$\dots$
$\dfrac{(n-1)}{2} \equiv \dfrac{(n-1)}{2} \pmod{n}$
$n-1 \equiv -1 \pmod{n}$
$n-2 \equiv -2 \pmod{n}$
$n-3 \equiv -3 \pmod{n}$
$\dots$
$\dfrac{(n+1)}{2} \equiv -\dfrac{(n-1)}{2} \pmod{n}$
Since $n$ is odd, exponentiation preserves the sign. And so
$$0^n + 1^n + 2^n + \dots + \left(\dfrac{n-1}{2}\right)^n + \left(\dfrac{n+1}{2}\right)^n + \dots + (n-2)^n + (n-1)^n + n^n$$
is equivalent to
$$1^n + 2^n + \dots + \left(\dfrac{n-1}{2}\right)^n - \left(\dfrac{n-1}{2}\right)^n + \dots - 2^n - 1^n$$
modulo $n$, and so the sum becomes $0$ modulo $n$. Note that the exponent could be replaced by any odd integer and the statement will still hold.
EDIT: Here is the example you requested in the comments.
Let's say we have the list 5, 6, 7, 8, 9, 10, 11, with $n=7$.
Okay, so the first thing I will do is to find their representatives in $\mod 7$ between $0$ and $6$ inclusive.
So,
5, 6, 7, 8, 9, 10, 11 becomes 5, 6, 0, 1, 2, 3, 4.
Now, let's look at $(n-1)/2$. For $n=7$, this number is 3. That is the cut off for the positive terms. The rest of them I turn them into negatives:
$5, 6, 7, 8, 9, 10, 11$ becomes
$5, 6, 0, 1, 2, 3, 4,$ which is
$7-2, 7-1, 0, 1, 2, 3, 7-3$, which becomes
$-2, -1, 0, 1, 2, 3, -3$.
Now, take any odd power of these numbers, sum, you get 0 in modulo 7.
Technically, I could've gone directly from the original list to $-2, -1, 0, 1, 2, 3, -3$, without going through the intermediate step, but I wanted to illustrate how the proof applies to this particular example.