# suppose that $n$ is natural number and even, show that $n \nmid 1^n +2^n+3^n + \ldots (n-1)^n$.

suppose that $n$ is natural number and even, show that $n \nmid 1^n +2^n+3^n + \ldots (n-1)^n$.

so I put $n=2k$ and I supposed $n \mid 1^n +2^n+3^n + \ldots (n-1)^n$ then with a little calculation we find out if $k$ is odd we have contradiction,but if $k$ is even we don't have any contradiction but still something is wrong but I couldn't find it,please help me with this,or any other solution.thanks.

• Note that the square of a number is either of the form $4k$ or $4k+1$ – zed111 Jan 11 '15 at 18:06
• Yes... $8k+1 = 4k'+1$ – Joffan Jan 11 '15 at 18:14

Let $n=2^i(2j+1)$. As $n$ is even, we have $i\ge 1$. And of course $n\ge 2^i>i$. So $n\ge i+1$

Let $S_n=\sum_{k=1}^{n-1}k^n$

1. For any even number $k$, $k^n$ will be a multiple of $2^n$, and then of $2^{i+1}$.
2. For any odd number, $k^n\equiv 1[2^{i+1}]$, by induction on $i$:

a. It's true for $i=1$ that $(2x+1)^2\equiv 1[4]$

b. Suppose it's true for $i$, then $z=(2x+1)^{2^{i}}\equiv 1[2^{i+1}]$

$$(2x+1)^{2^{i+1}}=z^2=(2^{i+1}y+1)^2=2^{i+2}(2^iy^2+y)+1\equiv1[2^{i+2}]$$

c. So $k^n=k^{2^i(2j+1)}\equiv1^{(2j+1)}[2^{i+1}]\equiv 1[2^{i+1}]$

3. There are exactly $2^{i-1}(2j+1)$ odd numbers in $S_n$, so $$S_n\equiv 2^{i-1}(2j+1)[2^{i+1}]\equiv 2^{i-1}[2^i]$$

As $2^i$ divides $n$ and not $S_n$, then $n$ does not divide $S_n$

• +1. For the benefit of others, the notation $\equiv a[b]$ here is just a shorthand for $\equiv a \pmod b$. – Erick Wong Jan 14 '15 at 1:13

Some partial result. We can show that if $n$ is even and divides the given sum then $n=2^{M}$ for some $1\leq M<n-1$. Let $n=2k_1$ then $$1^n+2^n+3^n+...+(n-1)^n=1^{2k_1}+2^{2k_1}+3^{2k_1}+...+(2k_1-1)^{2k_1}$$ Since $n$ is even and divides the sum it must be the case $$2(1^{2k_1}+2^{2k_1}+3^{2k_1}+...+(k_1-1)^{2k_1})+k^{2k_1}_1\equiv0\mod{2k_1}$$ implying that $$k_1\equiv0\mod{2}$$ and $$1^{2k_1}+2^{2k_1}+3^{2k_1}+...+(k_1-1)^{2k_1}\equiv0\mod{k_1}$$ Now set $k_1=2k_2$ then from the very last result we obtain $$1^{2k_1}+2^{2k_1}+3^{2k_1}+...+(k_1-1)^{2k_1}=1^{4k_2}+2^{4k_2}+3^{4k_2}+...+(2k_2-1)^{4k_2}\equiv2(1^{4k_2}+2^{4k_2}+3^{4k_2}+...+(k_2-1)^{4k_2})+k^{4k_2}_2\equiv0\mod{2k_2}$$ Again we would get $$k_2\equiv0\mod{2}$$ and $$1^{4k_2}+2^{4k_2}+3^{4k_2}+...+(k_2-1)^{4k_2}\equiv0\mod{k_2}$$ Repeating this process $m$-times we get $$k_m\equiv0\mod{2}$$ and $$1^{2^mk_m}+2^{2^mk_m}+3^{2^mk_m}+...+(k_m-1)^{2^mk_m}\equiv0\mod{k_m}$$ where the recursive relation $k_{m-1}=2k_m$ holds. Eventually you will reach a point where for some $M-1\in\mathbb{N}$ we have $k_{M-1}=2$ then $$2\equiv0\mod{2}$$ and $$1^{2^M\cdot2}+(2\cdot 1-1)^{2^M\cdot2}\equiv0\mod{2}$$ which is true. Therefore $n=2k_1=2^2k_2=...=2^{M-1}k_{M-1}=2^M$.