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

  • Context: MHB 
  • Thread starter Thread starter mathmari
  • Start date Start date
Click For Summary

Discussion Overview

The discussion revolves around the divisibility of the sum \(1^m + 2^m + \ldots + (n-1)^m\) by \(n\), where \(m\) and \(n\) are positive integers. Participants explore the conditions under which this statement holds, examining both theoretical aspects and specific examples.

Discussion Character

  • Exploratory
  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • One participant proposes that the sum \(s = 1^m + 2^m + \ldots + (n-1)^m\) is divisible by \(n\) and provides a method involving modular equivalences.
  • Others challenge this claim by testing specific values of \(m\) and \(n\), finding that the results do not hold for certain cases, suggesting that additional conditions may be necessary.
  • A later reply indicates that \(m\) must be odd for the original claim to potentially hold true.
  • Another participant suggests that \(n\) should also be odd, referencing an example to illustrate why the claim fails otherwise.
  • There is a discussion about using binomial expansion to analyze the expression \((n-k)^m\) and its implications for the divisibility condition.
  • Participants explore the relationship between the sum and its modular properties, particularly under the assumption that both \(m\) and \(n\) are odd.

Areas of Agreement / Disagreement

Participants do not reach a consensus on the original claim's validity. There are competing views regarding the necessary conditions for \(m\) and \(n\), and the discussion remains unresolved regarding the generality of the divisibility statement.

Contextual Notes

Participants note that the validity of the divisibility condition may depend on the parity of \(m\) and \(n\), but the specific implications of these conditions are not fully resolved.

mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hey! :o

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

Similar threads

Undergrad Evaluation of the sum 1^m+3^m+5^m+ ....................(2n+1)^{m}
  • · Replies 1 ·
Replies
1
Views
2K
Graduate A global version of the implicit function theorem
  • · Replies 0 ·
Replies
0
Views
630
MHB Number of natural numbers that have primitive roots
  • · Replies 5 ·
Replies
5
Views
2K
MHB What is the remainder when m+n is divided by 1000 in a trigonometric challenge?
  • · Replies 2 ·
Replies
2
Views
1K
Undergrad Optimization problem with multiple outputs: impossible?
  • · Replies 6 ·
Replies
6
Views
3K
MHB Digit sum rule for the divisibility by 9
  • · Replies 2 ·
Replies
2
Views
2K
MHB Solve √(x^2+3x+7)-√(x^2-3x+9)+2=0
  • · Replies 5 ·
Replies
5
Views
2K
High School General explicit solution to polynomial interpolation
  • · Replies 3 ·
Replies
3
Views
2K
MHB Solving $(m,n)$ for $m^2-2mn+14n^2=217$
  • · Replies 5 ·
Replies
5
Views
2K
MHB Is the perimeter numerically equal to the area in this equation?
  • · Replies 2 ·
Replies
2
Views
1K