# Prove $a^n+1$ is divisible by $a + 1$ if $n$ is odd [duplicate]

Prove $$a^n+1$$ is divisible by $$a + 1$$ if $$n$$ is odd:

We know $$a$$ cannot be $$-1$$ and the $$n \in \mathbb{N}$$. Since $$n$$ must be odd, we can rewrite $$n$$ as $$2k+1$$. Now we assume it holds for prove that it holds for the next term.

$$a^{2(k+1)+1}+1$$ $$=a^{2k+3}+1$$ $$=a^3\cdot a^{2k}+1$$ $$=(a^3+1)\cdot a^{2k} -a^{2k}+1$$

Im not sure on what to do next. Since $$a^{2k}$$ means that the exponential term will be even and thus you cant use the fact that $$a^n+1$$ is divisible by $$a + 1$$ if $$n$$ is odd.

## marked as duplicate by Bill Dubuque divisibility StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Apr 7 at 17:47

• Why should $a$ not be $-1$? The statement not only still makes sense, but it's true as well. – Saucy O'Path Apr 7 at 17:24
• First show $X+1$ divides $X^n +1$ as polynomials using factor theorem. Then the rest follows. – Ignorant Mathematician Apr 7 at 17:24

Use the fact that, since $$n$$ is odd\begin{align}a^n+1&=a^n-(-1)^n\\&=\bigl(a-(-1)\bigr)\bigl(a^{n-1}+(-1)a^{n-2}+(-1)^2a^{n-3}+\cdots\bigr)\\&=(a+1)(a^{n-1}-a^{n-2}+\cdots+1).\end{align}
For the inductive step, as $$(a+1)$$ divides $$a^{n-2}+1$$(as if $$n$$ is odd then also $$n-2$$ is odd), consider $$(a^n+1)-(a^{n-2}+1)=a^{n-2}(a^2-1)=a^{n-2}(a+1)(a-1)$$ As, $$(a+1)$$ divides $$a^{n-2}+1$$ and also divides $$(a^n+1)-(a^{n-2}+1)$$, we can conclude that $$(a+1)$$ divides $$(a^n+1)$$.
Now we consider $$Q(a)=a+1$$ and $$P(a)=a^n+1$$. Note that both P and Q are monic polynomial.
$$Q|P \iff P(-1)=0$$ since $$P(-1)=(-1)^n+1$$ then $$Q|P\iff n$$ is odd.