MHB Show that 1^m+2^m+....+(n-2)^m+(n-1)^m is divisible by n

[mathmari]

Hey!

Show that if $m,n$ are positive integers, then $1^m+2^m+...+(n-2)^m+(n-1)^m$ is divisible by $n$.
(Hint: Let $s=1^m+2^m+...+(n-2)^m+(n-1)^m$. Obviously $s=(n-1)^m+(n-2)^m+...+2^m+1^m$.
Consider these relations as equivalent modn and add them.)

$$1^m+2^m+...+(n-2)^m+(n-1)^m=((n-1)^m+(n-2)^m+...+2^m+1^m)modn$$
$$(n-1)^m+(n-2)^m+...+2^m+1^m=(1^m+2^m+...+(n-2)^m+(n-1)^m)modn$$
By adding them we get:
$$(1^m+(n-1)^m)+(2^m+(n-2)^m)+...+((n-2)^m+2^m)+((n-1)^m+1^m)=((n-1)^m+1^m)+((n-2)^m+2^m)+...+(2^m+(n-2)^m)+(1^m+(n-1)^m))modn$$
That means that:
$$n|[(1^m+(n-1)^m)+(2^m+(n-2)^m)+...+((n-2)^m+2^m)+((n-1)^m+1^m)]-[((n-1)^m+1^m)+((n-2)^m+2^m)+...+(2^m+(n-2)^m)+(1^m+(n-1)^m))]$$
Or not??
And that is equal to $$n|0$$
Is this correct?

 

[Opalg]

Something seems to be wrong here. I tested this result by trying small values of $m$ and $n$:

$(m=1,n=4)\quad 1^1 + 2^1 + 3^1 = 6$, which is not a multiple of $4$;

$(m=2, n=3)\quad 1^2 + 2^2 = 5$, which is not a multiple of $3$;

$(m=4, n=5)\quad 1^4 + 2^4 + 3^4 + 4^4 = 354$, which is not a multiple of $5$.​

Is there some additional condition missing from the statement of the problem?

 

[mathmari]

Something seems to be wrong here. I tested this result by trying small values of $m$ and $n$:

$(m=1,n=4)\quad 1^1 + 2^1 + 3^1 = 6$, which is not a multiple of $4$;

$(m=2, n=3)\quad 1^2 + 2^2 = 5$, which is not a multiple of $3$;

$(m=4, n=5)\quad 1^4 + 2^4 + 3^4 + 4^4 = 354$, which is not a multiple of $5$.​

Is there some additional condition missing from the statement of the problem?

I read the exercise again and realized that there is also the condition that $m$ is odd..

 

[I like Serena]

Hi! :)

I read the exercise again and realized that there is also the condition that $m$ is odd..

I think you also need the additional condition that $n$ is odd as well.
See Opalg's first example to see why it won't work otherwise.

Can you make a binomial expansion of $(n-k)^m$?
And find the remainder $\mod n$?

 

[Opalg]

Show that if $m,n$ are positive integers, then $1^m+2^m+...+(n-2)^m+(n-1)^m$ is divisible by $n$.
(Hint: Let $s=1^m+2^m+...+(n-2)^m+(n-1)^m$. Obviously $s=(n-1)^m+(n-2)^m+...+2^m+1^m$.
Consider these relations as equivalent modn and add them.)

$$1^m+2^m+...+(n-2)^m+(n-1)^m=((n-1)^m+(n-2)^m+...+2^m+1^m)modn$$
$$(n-1)^m+(n-2)^m+...+2^m+1^m=(1^m+2^m+...+(n-2)^m+(n-1)^m)modn$$
By adding them we get:
$$(1^m+(n-1)^m)+(2^m+(n-2)^m)+...+((n-2)^m+2^m)+((n-1)^m+1^m)=((n-1)^m+1^m)+((n-2)^m+2^m)+...+(2^m+(n-2)^m)+(1^m+(n-1)^m))modn$$

On the assumption that $m$ and $n$ are both odd, I would modify your approach just a bit, to write it as $$s=(n-1)^m+(n-2)^m+...+2^m+1^m,$$
$$s=1^m+2^m+...+(n-2)^m+(n-1)^m.$$
By adding them we get:
$$2s = \bigl((n-1)^m + 1^m\bigr)+\bigl((n-2)^m+ 2^m\bigr)+ \ldots +\bigl(2^m + (n-2)^m\bigr)+\bigl(1^m + (n-1)^m\bigr).$$ Can you continue from there?

 

[mathmari]

Can you make a binomial expansion of $(n-k)^m$?
And find the remainder $\mod n$?

Do you mean that $(n-k)^m= \sum_{i=0}^{m} \binom{m}{i}{n^{m-i}(-k)^{m}}$ ?

Is it true that: $(n-k)^m=-k(\mod n)$ ?

On the assumption that $m$ and $n$ are both odd, I would modify your approach just a bit, to write it as $$s=(n-1)^m+(n-2)^m+...+2^m+1^m,$$
$$s=1^m+2^m+...+(n-2)^m+(n-1)^m.$$
By adding them we get:
$$2s = \bigl((n-1)^m + 1^m\bigr)+\bigl((n-2)^m+ 2^m\bigr)+ \ldots +\bigl(2^m + (n-2)^m\bigr)+\bigl(1^m + (n-1)^m\bigr).$$ Can you continue from there?

$[2s]=[\bigl((n-1)^m + 1^m\bigr)+\bigl((n-2)^m+ 2^m\bigr)+ \ldots +\bigl(2^m + (n-2)^m\bigr)+\bigl(1^m + (n-1)^m\bigr)]=[\bigl((n-1)^m + 1^m\bigr)]+[\bigl((n-2)^m+ 2^m\bigr)]+\ldots +[\bigl(2^m + (n-2)^m\bigr)]+[\bigl(1^m + (n-1)^m\bigr)]=([n-1]^m+[1]^m)+([n-2]^m+[2]^m)+\ldots +([2]^m+[n-2]^m)+([1]^m+[n-1]^m)=([-1]^m+[1]^m)+([-2]^m+[2]^m)+ \ldots +([2]^m+[-2]^m)+([1]^m+[-1]^m)=(-[1]^m+[1]^m)+(-[2]^m+[2]^m)+ \ldots +([2]^m-[2]^m)+([1]^m-[1]^m)=0+0+ \ldots +0+0=0$

So the remainder of the division of $2s$ and $n$ is $0$, so the remainder of the division of $s$ and $n$ is also $0$.

Is this correct?

 

[I like Serena]

Do you mean that $(n-k)^m= \sum_{i=0}^{m} \binom{m}{i}{n^{m-i}(-k)^{m}}$ ?

Yep.

Is it true that: $(n-k)^m=-k(\mod n)$ ?

Almost.
That should be
$$(n-k)^m \equiv -k^m \pmod n$$
when $m$ is odd.