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.

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.

share|improve this question
3  
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

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer
    
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$.

share|improve this answer
    
Thank you for your response! –  A.Magnus Feb 13 at 15:26

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.