Indian Statistical Institute B.Math & B.Stat : Number Theory

Let $k$ be any odd integer greater that 1. Then show that $1^k+2^k+3^k+\dots \dots+2006^k$ is divisible by 2013021. We will prove the general case. Let $S= 1^k+2^k+3^k+\dots \dots+n^k$ where $n \geq 2$ and $n\in \mathbb{N}$. $2S = 1^k+2^k+3^k+\dots \dots+n^k + 1^k+2^k+3^k+\dots \dots+n^k = (1^k+n^k)+(2^k+(n-1)^k)+\dots \dots+(n^k+1^k)$ Using the result, $n^k+m^k$ is always divisible by $n+m$ if $k$ is odd we see that $2S$ is divisible by $(n+1)$ Again $2S = 1^k+2^k+3^k+\dots \dots+n^k + 1^k+2^k+3^k+\dots \dots+n^k$ $= (1^k+(n-1)^k)+(2^k+(n-2)^k)+\dots \dots+((n-1)^k+1^k)+2n^k$ Using the same result and noting that $2n^k$ is divisible by $n$ we see that $2S$ is divisible by $n$. Now both $n$ an $n+1$ divides $2S$ and $g.c.d(n.n+1)=1$ we see that $n(n+1)$ divides $2S$ this implies $\frac{n(n+1)}{2}$ divides $S$. ( $n(n+1)$ is always even) In the given problem $n=2006$, thus $1^k+2^k+3^k+\dots \dots+2006^k$ is divisible by $\frac{2006(2006+1)}{2}=2013021$