4
$\begingroup$

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.

$\endgroup$
4
  • 3
    $\begingroup$ 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$. $\endgroup$
    – Braindead
    Feb 12, 2014 at 14:29
  • $\begingroup$ 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$. $\endgroup$ Feb 12, 2014 at 15:16
  • $\begingroup$ @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. $\endgroup$
    – A.Magnus
    Feb 14, 2014 at 15:27
  • $\begingroup$ @LoveMath I edited my answer to include the example. $\endgroup$
    – Braindead
    Feb 14, 2014 at 17:01

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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! $\endgroup$
    – A.Magnus
    Feb 13, 2014 at 15:29
  • $\begingroup$ Solid Answer, nicely done. $\endgroup$
    – Newb
    Feb 14, 2014 at 17:02
2
$\begingroup$

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

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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