Dividing $n^k+1$ by $n+1$ if and only if $k$ is odd

Question

For that question, I can use modular arithmetic to prove divisibility. Look at the following: $$n \equiv-1\mod(n+1)$$ raising to $k^{th}$ power, if $k$ is odd, then $$n^k \equiv(-1)^k \equiv-1\mod(n+1)$$ hence $$n^k+1 \equiv0\mod(n+1)$$ as desired. On the other hand, if $k$ is odd, then $$n^k \equiv(-1)^k \equiv1\mod(n+1)$$ hence $$n^k+1 \equiv2\mod(n+1)$$

However, is it possible to come up with a divisibility proof? i.e. if $(n+1)k = (n^k+1)$, what is $k$?? I applied a long division but found $(n^{k-1}-n^{k-2}+n^{k-3}-n^{k-4}...)$ which I am suspicious about as I found in my instructor notes that if $k$ is odd, then $(n^{k}+1)=(n+1)(n^{k-1}-n^{k-2}...-n+1)$. This solution, the instructor's one, feels reasonable as when multiplying these terms, the result is $n^k+1$. What about mine?, how to connect it to the parity of $k$ as well?

Answer 1

For your division, what is the last term? The general term will be $(-1)^{r-1}n^{k-r}$ and you will end when $r=k$ with $(-1)^{k-1}n^0=(-1)^{k-1}$.

Here you get $+1$ when $k$ is odd and $-1$ when $k$ is even. All that remains is to compute the remainder.

One way of doing this is simply to use the remainder theorem - if $$p(n)=(n+1)q(n)+r$$ using polynomial division, then $p(-1)=r$, and apply it to the polynomial $p(n)=n^k+1$

Indeed, it is not necessary to compute $q(n)$ specifically to use this result.

Answer 2

Write $n^k+1=(n+1)q(n)+r(n)$, where $\deg(r)<\deg(q)$.

If $n+1\mid n^k+1$ then $r(n)=0$, so $n^k+1=(n+1)q(n)$. Letting $n=-1$ we get $(-1)^k+1=0$, so $k$ is odd. If $k$ is odd then $n=-1$ is a root, so $n+1\mid n^k+1$.

Answer 3

$((n+1)-1)^k +1=$

$(n+1)^k + k(-1)(n+1)^{k-1}+......$

$..+k(n+1)(-1)^{k-1}+(-1)^k +1.$

All terms, except the last term $(-1)^k$, in the binomial expansion have a factor $(n+1)$.

For odd $k$: $(-1)^k +1=0.$