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

  • MHB
  • Thread starter mathmari
  • Start date
In summary, for a number to be divisible by another number, it must be a factor of the first number with no remainder. The statement 1^m+2^m+....+(n-2)^m+(n-1)^m is divisible by n can be proven using mathematical induction, where the variable "m" represents the exponent or power. This statement is only valid for positive integer values of n and is important in mathematics for its applications in number theory and as an illustration of mathematical induction.
  • #1
mathmari
Gold Member
MHB
5,049
7
Hey! :eek:

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?
 
Mathematics news on Phys.org
  • #2
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?
 
  • #3
Opalg said:
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..
 
  • #4
Hi! :)

mathmari said:
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$?
 
  • #5
mathmari said:
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?
 
  • #6
I like Serena said:
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)$ ?

Opalg said:
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?
 
  • #7
mathmari said:
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.
 

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

What does it mean for a number to be divisible by another number?

For a number to be divisible by another number, it means that the division of the first number by the second number results in a whole number with no remainder. In other words, the second number is a factor of the first number.

How do you prove that 1^m+2^m+....+(n-2)^m+(n-1)^m is divisible by n?

This can be proven using mathematical induction. First, we show that the statement is true for n=1. Then, we assume that the statement is true for some integer k. Using this assumption, we can show that the statement is also true for k+1. This completes the proof by induction and shows that the statement is true for all positive integers.

What is the significance of the variable "m" in the equation?

The variable "m" represents the exponent or power to which each term is raised. This allows us to generalize the statement for all powers, rather than just a specific power.

Can this statement be proven for non-integer values of n?

No, the statement is only valid for positive integer values of n. This can be seen in the fact that the sum of consecutive integers is always a whole number, and the statement would not hold true if n was a non-integer value.

Why is this statement important in mathematics?

The statement is important because it allows us to prove the divisibility of a sum of consecutive integers, which has many applications in number theory and other areas of mathematics. It also demonstrates the power of mathematical induction as a proof technique.

Similar threads

Replies
5
Views
1K
Replies
1
Views
946
Replies
0
Views
983
Replies
2
Views
1K
Replies
5
Views
2K
Replies
3
Views
1K
Back
Top