8
$\begingroup$

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.

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

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$

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.