$k^2+k+1=(k-k_1)(k-k_2),k_{1,2}=\frac{-1\pm \sqrt{-3}}{2}.$ $(k_i+1)^n-k_i^n-1=(-k_j)^n-k_i^n-1=-1-exp(\frac{2\pi ni}{3})-exp(\frac{-2\pi ni}{3})=0.$

Please give me elementary solution !

WakeUp wrote: Let $n$ be a positive integer not divisible by $2$ or $3$. Prove that for all integers $k$, the number $(k+1)^n-k^n-1$ is divisible by $k^2+k+1$. gold46 wrote: Please give me elementary solution ! I hope this is more elementary solution. $2\not|n\implies n$ is an odd integer. If $n=1$ then $(k+1)^n-k^n-1=k+1-k-1=0$ which is obviously a multiple of $k^2+k+1$ If $n>1$ then let $n=2a+1$ where $a\in\mathbb Z^+$ Then $(k+1)^n=(k+1)(k^2+2k+1)^a\equiv (k+1)k^a\mod k^2+k+1$ Then $(k+1)^n\equiv (k+1)k^a\equiv (k^2+k)k^{a-1}\equiv -k^{a-1} \mod k^2+k+1$ $k^3-1=(k-1)(k^2+k+1)\implies k^2+k+1|k^3-1$ $k^3\equiv 1\mod k^2+k+1\implies k^{m+3}\equiv k^m\mod k^2+k+1$ So if $m\equiv m'\mod 3$ then $k^m\equiv k^{m'}\mod k^2+k+1$ (You can use induction) $3\not|n\implies 2a+1\not\equiv 0\mod 3\implies a\not\equiv 1\mod 3$ If $a\equiv 0\mod 3$ then $a-1\equiv 2\mod 3$ and $2a+1\equiv 1\mod 3$ Then $(k+1)^n\equiv -k^2\mod k^2+k+1$ Also $k^n\equiv k\mod k^2+k+1$ Then $(k+1)^n-k^n-1\equiv -k^2-k-1\equiv -(k^2+k+1)\equiv 0\mod k^2+k+1$ If $a\equiv 2\mod 3$ then $a-1\equiv 1\mod 3$ and $2a+1\equiv 2\mod 3$ Then $(k+1)^n\equiv -k\mod k^2+k+1$ Also $k^n\equiv k^2\mod k^2+k+1$ Then $(k+1)^n-k^n-1\equiv -k-k^2-1\equiv -(k^2+k+1)\equiv 0\mod k^2+k+1$ In both cases $k^2+k+1$ divides $(k+1)^n-k^n-1$ as required.

Note that $k^2+k+1=(k-\omega )(k-\omega ^2)$.Now set $k=\omega $,then $(k+1)^n-k^n-1$ reduced to $\omega ^2+\omega +1$ because $gcd(6,n)=1$,similar for $k=\omega ^2$. Here $\omega ^3=1$ with $\omega +1=-\omega ^2$.

mathmdmb wrote: Note that $k^2+k+1=(k-\omega )(k-\omega ^2)$.Now set $k=\omega $,then $(k+1)^n-k^n-1$ reduced to $\omega ^2+\omega +1$ because $gcd(6,n)=1$,similar for $k=\omega ^2$. Here $\omega ^3=1$ with $\omega +1=-\omega ^2$. Why does it reduce to $\omega ^2+\omega +1$?

Well, it was said that $\omega +1=-\omega ^2$. Now when setting $k=\omega $, then $(k+1)^n-k^n-1$ becomes $(\omega+1)^n-\omega^n-1 = (-\omega^2)^n-\omega^n-1 = -(\omega^{n})^2-\omega^n-1$, so in fact it reduces to $-(\omega ^2+\omega +1) = 0$ (remember $\gcd(6,n)=1$).