Moscow Middle School Math Olympiad Question. Can you prove this challenging number theory problem?

This is a challenging question from Moscow middle school mathematical Olympiad competition . Prove 1^k + 2^k + ...+ n^k is divisible by 1+2+...+n. In this video, we'll discuss a beautiful method to prove this question.

Recommended playlist:

[DrWangUSA]

If n is odd, how to prove n and (n+1) are relatively prime? let n=2k+1, then (n+1)/2=k+1. let k1 is the common factor of n and (n+1)/2, then exist a and b, such that n=a*k1 and (n+1)/2=b*k1, i.e, 2k+1=a*k1 and k+1=b*k1, this implies (2b-a)k1=1, we have k1=1. therefore, the common factor must be 1.

[jameswayne]

a very challenging problem, well explained

[Legend-mrci]

Can't we just do this

(1+2+3+....+n)^k

So

(n(n+1)/2)^k

And it's obviously divisible by

(n(n+1)/2)^1

[Biologymus]

maybe easier to prove by induction over n.

[ariezelezniak]

how can one derive the two factors of x^n + y^n for n odd? can someone point me in the correct direction?