# Generalization of “Sum of cube of any 3 consecutive integers is divisible by 3”

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.

-
Hint: Use modular arithmetic. If you have $1,2,3,4,\dots, n$, in modulo $n$, you have $1,2,3,\dots, -3,-2,-1,0$. If $n$ is odd, then $(-a)^n = -a^n$, so that would cancel with $a^n$. –  Braindead Feb 12 at 14:29
Why doesn't $a-3,a-2,a-1,a,a+1,a+2,a+3$ work? Add those $7$ numbers together and you get $7a$, which is divisible by $7$. –  John Habert Feb 12 at 15:16
Thanks for your response! –  A.Magnus Feb 13 at 15:29
@Braindead: Do give me example. Suppose you have 5, 6, 7, 8, 9, 10, 11 (mod 7), how do you turn them into -3, -2, -1, 0, 1, 2, 3 (mod 7) such that they will be cancel out? Thanks. –  A.Magnus Feb 14 at 15:27
@LoveMath I edited my answer to include the example. –  Braindead Feb 14 at 17:01

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.

-
Thanks for your elaborate response! I actually came up with my own, but mine is good only for prime, yours is more comprehensive. (I used binomial coefficient, when n is prime then all coefficients will be divisible by n, etc.) Thanks again! –  A.Magnus Feb 13 at 15:29
Solid Answer, nicely done. –  Newb Feb 14 at 17:02

The remainders modulo $2k+1$ can be (re)written as $0,\pm1,\pm2,\ldots,\pm k$. By rising them each to any positive odd power of our choosing, they will maintain their sign, while their absolute values will be pair-wise equal, so ultimately their sum will be divisible through $n=2k+1$.

-
Thank you for your response! –  A.Magnus Feb 13 at 15:26